Heuristic, Branch-and-Bound Solver and Improved Space Reduction for the Median of Permutations Problem

Given a set \(\mathcal {A}\subseteq \mathbb {S}_n\) of m permutations of \(\{1,2,\ldots ,n\}\) and a distance function d, the median problem consists of finding a permutation \(\pi ^*\) that is the “closest” of the m given permutations. Here, we study the problem under the Kendall-\(\tau \) distance which counts the number of order disagreements between pairs of elements of permutations. In this article, we explore this NP-hard problem using three different approaches: a well parameterized heuristic, an improved space search reduction technique and a refined branch-and-bound solver.