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 metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620459
Contributor : Guillaume Blin <>
Submitted on : Wednesday, February 13, 2013 - 11:58:30 AM
Last modification on : Monday, July 20, 2020 - 12:34:50 PM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:40 AM

File

Finding_the_median_of_three_pe...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620459, version 1

Citation

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⟩

Share

Metrics

Record views

451

Files downloads

644