Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Optimal Embedding of Locally Twisted Cubes into Grids Read chapter Read first chapter

2017 | OriginalPaper | Chapter

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

Authors : Ante Ćustić, Ehsan Iranmanesh, Ramesh Krishnamurti

Published in: Algorithms and Discrete Applied Mathematics

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Axiomatic Characterization of the Interval Function of a Bipartite Graph
next chapter On Structural Parameterizations of Graph Motif and Chromatic Number
Literature
1.
Brams, S.J.: Mathematics and Democracy - Designing Better Voting and Fair-division Procedures. Princeton University Press, Princeton (2007)MATH
2.
Brams, S.J., Fishburn, P.C.: Proportional representation in variable-size legislatures. Soc. Choice Welf. 1, 211–229 (1984)CrossRefMATH
3.
Brams, S.J., Fishburn, P.C.: Some logical defects of the single transferable vote. In: Choosing an Electoral System: Issues and Alternatives (1984)
4.
Monroe, B.L.: Fully proportional representation. Am. Polit. Sci. Rev. 89(4), 925–940 (1995)CrossRef
5.
Chamberlin, J.R., Courant, P.N.: Representative deliberations and representative decisions: proportional representation and the Borda rule. Am. Polit. Sci. Rev. 77(3), 718–733 (1983)CrossRef
6.
Procaccia, A.D.: Computational voting theory: of the agents, by the agents, for the agents. Ph.D. thesis, Hebrew University (2008)
7.
Betzler, N., Slinko, A., Uhlmann, J.: On the computation of fully proportional representation. J. Artif. Intell. Res. (JAIR) 47, 475–519 (2013)MathSciNetMATH
8.
Skowron, P., Yu, L., Faliszewski, P., Elkind, E.: The complexity of fully proportional representation for single-crossing electorates. In: Vöcking, B. (ed.) SAGT 2013. LNCS, vol. 8146, pp. 1–12. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-41392-6_​1 CrossRef
9.
Yu, L., Chan, H., Elkind, E.: Multiwinner elections under preferences that are single-peaked on a tree. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (2013)
10.
Clearwater, A., Puppe, C., Slinko, A.: The single-crossing property on a tree. CoRR abs/1410.2272 (2014)
11.
Skowron, P., Faliszewski, P., Slinko, A.: Fully proportional representation as resource allocation: approximability results. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (2013)
12.
Skowron, P., Faliszewski, P., Slinko, A.: Achieving fully proportional representation is easy in practice. In: Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems (2013)
13.
Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)MATH
14.
15.
Glover, F., Punnen, A.P.: The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms. J. Oper. Res. Soc. 48(5), 502–510 (1997)CrossRefMATH
16.
Zemel, E.: Measuring the quality of approximate solutions to zero-one program- ming problems. Math. Oper. Res. 6(3), 319–332 (1981)MathSciNetCrossRefMATH
17.
Punnen, A.P., Sripratak, P., Karapetyan, D.: Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms. Theoret. Comput. Sci. 565(C), 77–89 (2015)MathSciNetCrossRefMATH
18.
Punnen, A.P., Kabadi, S.: Domination analysis of some heuristics for the traveling salesman problem. Discret. Appl. Math. 119(1–2), 117–128 (2002)MathSciNetCrossRefMATH
19.
Angel, E., Zissimopoulos, V.: On the quality of local search for the quadratic assignment problem. Discret. Appl. Math. 82(1–3), 15–25 (1998)MathSciNetCrossRefMATH
20.
Brams, S., Potthoff, R.F.: Proportional representation: broadening the options. Working papers, C.V. Starr Center for Applied Economics, New York University (1997)
21.
Baranyai, Z.: On the factorization of the complete uniform hypergraph. In: Infinite and Finite Sets: Proceedings of a Colloquium, Keszthely, June 25–July 1 1973, vol. 1, pp. 91–108 (1975). Dedicated to Paul Erdos on his 60th Birthday
Metadata
Title
Analysis of 2-Opt Heuristic for the Winner Determination Problem Under the Chamberlin-Courant System
Authors
Ante Ćustić
Ehsan Iranmanesh
Ramesh Krishnamurti
Copyright Year
2017
Book
Algorithms and Discrete Applied Mathematics

Print ISBN: 978-3-319-53006-2

Electronic ISBN: 978-3-319-53007-9

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-53007-9_10

Premium Partner

    Image Credits