Multiclass MinMax Rank Aggregation
This addresses rank aggregation challenges in fields like genomics, but it is incremental as it builds on existing distance measures and approximation methods.
The paper tackles the NP-hard problem of multiclass minmax rank aggregation under Kendall τ and Spearman footrule distances by proposing constant-approximation algorithms, with applications demonstrated on the Mallows model and genomic data.
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.