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 = {Yunlong Jiao and Anna Korba and Eric Sibony}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2971--2980}, year = {2016}, editor = {Maria Florina Balcan and Kilian Q. Weinberger}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 2971--2980 %U http://proceedings.mlr.press %V 48 %W PMLR %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 PY - 2016/06/11 DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-korba16 PB - PMLR SP - 2971 DP - PMLR EP - 2980 L1 - http://proceedings.mlr.press/v48/korba16.pdf UR - http://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 PMLR 48:2971-2980

Related Material