Hardness of Approximation of Rank Aggregation on Ulam Metric
Computational ComplexityData Structures and Algorithms
Summary
The authors study how hard it is to find good approximate solutions for two ranking problems using the Ulam distance, which measures how different two orderings are. They focus on the Ulam median problem (minimizing total distance to all permutations) and the Ulam center problem (minimizing the worst distance to any permutation). They prove it is very difficult (NP-hard) to even closely approximate these problems, and this remains true even with as few as four input permutations. Their results also show that no efficient method can guarantee small additive errors unless P equals NP.
Authors
Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong, Debarati Das, Tien Long Nguyen
Abstract
We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a permutation minimizing the sum of its Ulam distances to the input permutations, while in the \emph{Ulam center} problem the objective is to minimize the maximum such distance. Both problems are known to be NP-hard, but no explicit approximation hardness was previously known. We prove that, for every $\varepsilon>0$, it is NP-hard to approximate either Ulam median or Ulam center within a factor of $51/50-\varepsilon$, even when the input consists of only four permutations. We further show that unless P = NP, neither problem admits a polynomial-time additive approximation scheme. The hardness result for Ulam median is established via a reduction from MAX-E3-LIN-2. The corresponding hardness for Ulam center is then obtained through a reduction from Ulam median.