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- τ 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.

Authors

• Francis Y.L. Chin
• Xiaotie Deng Center on Frontiers of Computing Studies, School of Computer Science, Peking University, Beijing, China.
• Qizhi Fang Ocean University of China
• Shanfeng Zhu

Keywords

• Rank aggregation
• Kendall- τ distance
• Coherence
• Weighted ECC