License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07311.9
URN: urn:nbn:de:0030-drops-13024
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1302/
Go to the corresponding Portal

Simeone, Bruno ; Ricca, Federica ; Scozzari, Andrea

Weighted Voronoi Region Algorithms for Political Districting

pdf-format:
07311.SimeoneBruno.Pape.1302.pdf (0.3 MB)

Abstract

Automated political districting shares with electronic voting the aim of
preventing electoral manipulation and pursuing an impartial electoral
mechanism. Political districting can be modelled as multiobjective partitioning of a graph into connected components, where population equality and compactness must hold if a majority voting rule is adopted. This leads to the formulation of combinatorial optimization problems that are extremely hard to solve exactly. We propose a class of heuristics, based on discrete weighted Voronoi regions, for obtaining compact and balanced districts, and discuss some formal properties of these algorithms. Their performance has been tested on randomly generated rectangular grids, as well as on real-life benchmarks; for the latter instances the resulting district maps are compared with the institutional ones adopted in the Italian political elections from 1994 to 2001.

BibTeX - Entry

@InProceedings{simeone_et_al:DagSemProc.07311.9,
  author =	{Simeone, Bruno and Ricca, Federica and Scozzari, Andrea},
  title =	{{Weighted Voronoi Region Algorithms for Political Districting}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2008/1302},
  URN =		{urn:nbn:de:0030-drops-13024},
  doi =		{10.4230/DagSemProc.07311.9},
  annote =	{Keywords: Political districting, weighted Voronoi regions, graph partitioning, heuristics}
}

Keywords: Political districting, weighted Voronoi regions, graph partitioning, heuristics
Collection: 07311 - Frontiers of Electronic Voting
Issue Date: 2008
Date of publication: 15.01.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI