Multiclass MinMax Rank Aggregation

2017/01/28 by Pan Li, Olgica Milenkovic, Li, Pan +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Artificial Intelligence (cs.AI) #FOS: Biological sciences #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Quantitative Methods (q-bio.QM) #cs.AI #cs.LG #q-bio.QM #stat.ML

paper · pdf · doi:10.48550/arxiv.1701.08305

arxiv created 2017/01/28 · arxiv updated 2017/02/06

Abstract

We introduce a new family of minmax rank aggregation problems under two distance measures, the Kendall τ and the Spearman footrule. As the problems are NP-hard, we proceed to describe a number of constant-approximation algorithms for solving them. We conclude with illustrative applications of the aggregation methods on the Mallows model and genomic data.

Related

• Rank Aggregation: New Bounds for MCx
• A Novel Distance-Based Approach to Constrained Rank Aggregation
• An Axiomatic Approach to Constructing Distances for Rank Comparison and Aggregation
• Efficient space reduction techniques by optimized majority rules for the Kemeny aggregation problem and beyond
• Hardness of Median and Center in the Ulam Metric