Approximate and dynamic rank aggregation

Rank aggregation, originally an important issue in social choice theory, has become more and more important in information retrieval applications over the Internet, such as meta-search, recommendation system, etc. In this work, we consider an aggregation function using a weighted version of the normalized Kendall-tau distance. We propose a polynomial time approximation scheme, as well as a practical heuristic algorithm with the approximation ratio two for the NP-hard problem. In addition, we discuss issues and models for the dynamic rank aggregation problem. (C) 2004 Elsevier B.V. All rights reserved.