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

Title: Computing Kemeny rankings, parameterized by the average K-T distance
Creator: Betzler, Nadja; Fellows, Michael R.; Guo, Jiong; Niedemeier, Rolf; Rosamond, Frances A.
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
Publisher: University of Liverpool
Resource Type: conference paper
Date: 2008
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).
Subject: Kemeny rankings; Kemeny Scores; voting; fixed parameter algorithm
Identifier: http://hdl.handle.net/1959.13/45011
Identifier: uon:5956
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format