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 metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619773
Contributor : Guillaume Blin <>
Submitted on : Tuesday, August 26, 2014 - 1:56:26 PM
Last modification on : Monday, July 20, 2020 - 12:33:14 PM
Long-term archiving on: : Thursday, March 30, 2017 - 2:30:14 PM

File

medianeFinal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619773, version 1

Citation

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⟩

Share

Metrics

Record views

490

Files downloads

325