Analysis of 2-Opt Heuristic for the Winner Determination Problem Under the Chamberlin-Courant System

详细信息    查看全文

• 关键词：Domination analysis ; Proportional representation ; Chamberlin ; courant system ; 2 ; Opt heuristic
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10156
• 期：1
• 页码：107-117
• 丛书名：Algorithms and Discrete Applied Mathematics
• ISBN：978-3-319-53007-9
• 卷排序：10156

文摘

Winner determination problem under Chamberlin-Courant system deals with the problem of selecting a fixed-size assembly from a set of candidates that minimizes the sum of misrepresentation values. This system does not restrict the candidates to have a minimum number of votes to be selected. The problem is known to be NP-hard. In this paper, we consider domination analysis of a 2-Opt heuristic for this problem. We show that the 2-Opt heuristic produces solutions no worse than the average solution in polynomial time. We also show that the domination number of the 2-Opt heuristic is at least \({m-1 \atopwithdelims ()k-1}k^{n-1}\) for n voters and m candidates.