Invited Session Tue.2.H 3021

Tuesday, 13:15 - 14:45 h, Room: H 3021

Cluster 2: Combinatorial optimization [...]

Sampling, sorting and graph traversal: Algorithms for finding permutations


Chair: Alantha Newman



Tuesday, 13:45 - 14:10 h, Room: H 3021, Talk 2

Sarah Miracle
Mixing times of self-organizing lists and biased permutations

Coauthors: Prateek Bhakta, Dana Randall, Amanda P. Streib


Sampling permutations from Sn is a fundamental problem from probability theory. The nearest neighbor transposition chain is known to mix in time Θ(n3 log n) in the unbiased case and time Θ(n2) in the constant bias case. It was conjectured that the chain is always rapidly mixing when the inversion probabilities are positively biased, i.e., we put nearest neighbor pair x in order with bias 1/2 ≤ pxy ≤ 1 and out of order with bias 1-pxy. We prove the chain is rapidly mixing for two classes: "Choose Your Weapon,'' where we are given r1, … , rn-1 with ri ≥ 1/2 and px,y=rx for all x (the dominant player chooses the game, thus fixing their probability of winning), and "League hierarchies,'' where there are two leagues and players from the A-league have a fixed probability of beating players from the B-league, players within each league are divided into sub-leagues, and so forth recursively. Moreover, we also prove that the conjecture is false by exhibiting values for the pxy, with 1/2 ≤ pxy ≤ 1 for all x, but for which the chain will require exponential time to converge.



Tuesday, 14:15 - 14:40 h, Room: H 3021, Talk 3

Katarzyna Paluch
Simpler approximation of the maximum asymmetric traveling salesman problem

Coauthors: Khaled Elbassioni, Anke van Zuylen


We give a very simple approximation algorithm for the maximum asymmetric traveling salesman problem. The approximation guarantee of our algorithm is 2/3, which matches the best known approximation guarantee by Kaplan, Lewenstein, Shafrir and Sviridenko. Our algorithm is simple to analyze, and contrary to previous approaches, which need an optimal solution to a linear program, our algorithm is combinatorial and only uses maximum weight perfect matching algorithm.


  There are three major facts that should be watched out for in all payday loans in the United States. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.