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

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.