Finding the median of three permutations under the Kendall-tau distance

Guillaume Blin (1) , Maxime Crochemore (1, 2) , Sylvie Hamel (3) , Stéphane Vialette (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 DCS - Department of Computer Science
3 DIRO - Département d'Informatique et de Recherche Opérationnelle [Montreal]

Given m permutations π^1 , π^2, ... π^m of {1, 2, ... , n} and a distance function d, the median problem is to find a permutation π* that is the "closest" of the m given permutations. Here, we study the problem under the Kendall-τ distance that counts the number of pairwise disagreements between permutations. This problem is also known, in the context of rank aggregation, as the Kemeny Score Problem and has been proved to be NP-hard when m ≥ 4. In this article, we investigate the case m = 3.

Domaines: Algorithme et structure de données [cs.DS]

Guillaume Blin, Maxime Crochemore, Sylvie Hamel, Stéphane Vialette. Finding the median of three permutations under the Kendall-tau distance. 7th annual international conference on Permutation Patterns, Jul 2009, Firenze, Italy. pp.6. ⟨hal-00620459⟩