## 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**

**Abstract:**

Sampling permutations from *S*_{n} is a fundamental problem from probability theory. The nearest neighbor transposition chain is known to mix in time *Θ(n*^{3} *log* n) in the unbiased case and time *Θ(n*^{2}) 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 ≤ p*_{xy} ≤ 1 and out of order with bias *1-p*_{xy}. We prove the chain is rapidly mixing for two classes: "Choose Your Weapon,'' where we are given *r*_{1}, … , r_{n-1} with *r*_{i} ≥ 1/2 and *p*_{x,y}=r_{x} 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 **p*_{xy}, with *1/2 ≤ p*_{xy} ≤ 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**

**Abstract:**

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.