Space reduction constraints for the median of permutations problem.

Given a set A ⊆ S n of m permutations of { 1 , 2 , ... , 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 order disagreements between pairs of elements of two permutations. This problem has been proved to be NP-hard when m ≥ 4 , m even. In this article, which is a full version of the conference paper Milosz and Hamel (2016), we investigate new theoretical properties of A that solve the relative order between pairs of elements in median permutations of A , thus drastically reducing the search space of the problem. The resulting preprocessing of the problem is implemented with a Branch-and-Bound solving algorithm. We analyze its performance on randomly generated data and on real data. [ABSTRACT FROM AUTHOR]