Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/45011
- Computing Kemeny rankings, parameterized by the average K-T distance
Fellows, Michael R.;
Rosamond, Frances A.
- The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
- 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).
- 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
- University of Liverpool
fixed parameter algorithm
- Resource Type
- conference paper