Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Guillaume Blin Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 11:58:30 AM
Last modification on : Saturday, January 15, 2022 - 3:58:38 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:40 AM


Files produced by the author(s)


  • HAL Id : hal-00620459, version 1


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⟩



Les métriques sont temporairement indisponibles