Skip to Main content Skip to Navigation
Journal articles

Median of an odd number of permutations

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. This article is an extension of [4], where some nice combinatorial properties of the case m = 3 where stated without proof, to the general case m ≥ 3, m odd.
Document type :
Journal articles
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Guillaume Blin Connect in order to contact the contributor
Submitted on : Tuesday, August 26, 2014 - 1:56:26 PM
Last modification on : Saturday, January 15, 2022 - 3:58:07 AM
Long-term archiving on: : Thursday, March 30, 2017 - 2:30:14 PM


Files produced by the author(s)


  • HAL Id : hal-00619773, version 1


Guillaume Blin, Maxime Crochemore, Sylvie Hamel, Stéphane Vialette. Median of an odd number of permutations. Pure Mathematics and Applications, 2011, 21 (2), pp.161 - 175. ⟨hal-00619773⟩



Record views


Files downloads