NOVA. The University of Newcastle's Digital Repository

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/45011

Title

Computing Kemeny rankings, parameterized by the average K-T distance

Author/Creator

Betzler, Nadja;  Fellows, Michael R.;  Guo, Jiong;  Niedemeier, Rolf;  Rosamond, Frances A.

Institution

The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)

Description

The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Unfortunately, the problem is NP-hard. Extending our previous work [AAIM 2008], we show that the Kemeny Score of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter “average pairwise Kendall-Tau distance da”. We describe a fixed parameter algorithm with running time O16⌈da⌉ · poly).

Relation

2nd International Workshop on Computational Social Choice. Proceedings of the 2nd International Workshop on Computational Social Choice (COMSOC 2008) (Liverpool, UK 3-5 September, 2008) p. 85-96

Relation

http://www.csc.liv.ac.uk/~pwg/COMSOC-2008/proceedings.html

Date

2008

Publisher

University of Liverpool

Keyword(s)

Kemeny rankings;  Kemeny Scores;  voting;  fixed parameter algorithm

Resource Type

conference paper

Identifier

http://hdl.handle.net/1959.13/45011

---

Reviewed

Save/E-mail Citation

Citation Format

Plain Text Citation HTML Citation EndNote Format

E-mail Address

Subject

"Computing Kemeny rankings, parameterized by the average K-T distance"

 

OR