Controlling the distance to a Kemeny consensus without computing it

A Tractable Bound on Approximating Kemeny Aggregation.


Due to its numerous applications, rank aggregation has become a problem of major interest across many fields of the computer science literature. In the vast majority of situations, Kemeny consensus(es) are considered as the ideal solutions. It is however well known that their computation is NP-hard. Many contributions have thus established various results to apprehend this complexity. In this paper we introduce a practical method to predict, for a ranking and a dataset, how close the Kemeny consensus(es) are to this ranking. A major strength of this method is its generality: it does not require any assumption on the dataset nor the ranking. Furthermore, it relies on a new geometric interpretation of Kemeny aggregation that, we believe, could lead to many other results.

In Proceedings of the 32nd International Conference on Machine Learning (ICML)
Yunlong Jiao
Yunlong Jiao
Applied Machine Learning Research

My research interests include Deep Generative Models, Vision Language Models, Natural Language Processing, and Computational Biology.