Median of an odd number of permutations - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Pure Mathematics and Applications Année : 2011

Median of an odd number of permutations

Résumé

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.
Fichier principal
Vignette du fichier
medianeFinal.pdf (152.99 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00619773 , version 1 (26-08-2014)

Identifiants

  • HAL Id : hal-00619773 , version 1

Citer

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⟩
206 Consultations
326 Téléchargements

Partager

Gmail Facebook X LinkedIn More