Approximate Rank Aggregation (Preliminary Version)

摘要

In this paper, we consider algorithmic issues of the rank aggregation problem for information retrieval on the Web. We introduce a weighted version of the metric of the normalized Kendall-τ distance, originally proposed for the problem by Dwork, et al., [7] and show that it satisfies the extended Condorcet criterion. Our main technical contribution is a polynomial time approximation scheme, in addition to a practical heuristic algorithm with ratio 2 for the NP-hard problem.