Given a set A is contained in S_n of m permutations of [n] and a distance function d, the median problem consists of finding a permutation π~* that is the "closest" of the m given permutations. Here, we study the problem under the Kendall-τ distance which counts the number of pair-wise disagreements between permutations. This problem has been proved to be NP-hard when m ≥ 4, m even. In this article, we investigate new theoretical properties of A that will solve the relative order between pairs of elements in median permutations of A, thus drastically reducing the search space of the problem.
展开▼
