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

被引：0

作者：

Custic, Ante ^{[1
]}

Iranmanesh, Ehsan ^{[1
]}

Krishnamurti, Ramesh ^{[1
]}

机构：

[1] Simon Fraser Univ, Burnaby, BC V5A 1S6, Canada

来源：

ALGORITHMS AND DISCRETE APPLIED MATHEMATICS | 2017年 / 10156卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Domination analysis; Proportional representation; Chamberlin-courant system; 2-Opt heuristic; FULLY PROPORTIONAL REPRESENTATION; TRAVELING SALESMAN PROBLEM; ALGORITHMS; QUALITY;

D O I：

10.1007/978-3-319-53007-9_10

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 k-1)k(n-1) for n voters and m candidates.

引用

页码：107 / 117

页数：11

共 21 条

[1] Algorithms with large domination ratio [J].