Controlling the distance to a Kemeny consensus without computing it

Yunlong Jiao, Anna Korba, Eric Sibony
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2971-2980, 2016.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-korba16, title = {Controlling the distance to a Kemeny consensus without computing it}, author = {Jiao, Yunlong and Korba, Anna and Sibony, Eric}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2971--2980}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/korba16.pdf}, url = {https://proceedings.mlr.press/v48/korba16.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Controlling the distance to a Kemeny consensus without computing it %A Yunlong Jiao %A Anna Korba %A Eric Sibony %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-korba16 %I PMLR %P 2971--2980 %U https://proceedings.mlr.press/v48/korba16.html %V 48 %X 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.
RIS
TY - CPAPER TI - Controlling the distance to a Kemeny consensus without computing it AU - Yunlong Jiao AU - Anna Korba AU - Eric Sibony BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-korba16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2971 EP - 2980 L1 - http://proceedings.mlr.press/v48/korba16.pdf UR - https://proceedings.mlr.press/v48/korba16.html AB - 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. ER -
APA
Jiao, Y., Korba, A. & Sibony, E.. (2016). Controlling the distance to a Kemeny consensus without computing it. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2971-2980 Available from https://proceedings.mlr.press/v48/korba16.html.

Related Material