Ulam Rank Aggregation Is Hard to Approximate for Four Rankings

Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong +3

We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a ranking (permutation) minimizing the sum of its Ula…