An efficient approach for the rank aggregation problem

This paper presents some computational properties of the rank-distance, a measure of similarity between partial rankings. We show how this distance generalizes the Spearman footrule distance, preserving its good computational complexity: the rank-distance between two partial rankings can be computed in linear time, and the rank aggregation problem can be solved in polynomial time. Further, we present a generalization of the rank-distance to strings, which permits to solve the median string problem in polynomial time. This appears rather surprising to us given the fact that for other non-trivial string distances, such as edit-distance, this problem is NP-hard.