Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/45010
- Title
- Fixed-parameter algorithms for Kemeny Scores
- Author/Creator
-
Betzler, Nadja;
Fellows, Michael R.;
Guo, Jiong;
Niedermeier, Rolf;
Rosamond, Frances A.
- Institution
- The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
- Description
- The Kemeny Score problem is central to many applications in the context of rank aggregation. Given a set of permutations (votes) over a set of candidates, one searches for a "consensus permutation" that is "closest" to the given set of permutations. Computing an optimal consensus permutation is NP-hard. We provide first, encouraging fixed-parameter tractability results for computing optimal scores (that is, the overall distance of an optimal consensus permutation). Our fixed-parameter algorithms employ the parameters "score of the consensus", "maximum distance between two input permutations", and "number of candidates". We extend our results to votes with ties and incomplete votes, thus, in both cases having no longer permutations as input.
- Relation
- 4th International Conference on Algorithmic Aspects in Information and Management (AAIM 2008). Algorithmic Aspects in Information and Management: 4th International Conference, AAIM 2008 Proceedings (Shanghai, China 23-25 June, 2008) p. 60-71
- Publisher Link
- http://dx.doi.org/10.1007/978-3-540-68880-8_8
- Date
- 2008
- Publisher
- Springer Berlin
- Keyword(s)
-
Kemeny Scores;
rank aggregation;
consensus permutation;
fixed parameter algorithms;
permutations;
voting
- Resource Type
- conference paper
- Identifier
- http://hdl.handle.net/1959.13/45010
- Identifier
- ISBN:9783540688655
- Reviewed
12 Visitors
13 Hits
0 Downloads
