Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting

Cohen-Addad, V., Klein, P. N., & Marx, D. (2020). On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting. Retrieved from https://arxiv.org/abs/2009.00188.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Forschungspapier

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:2009.00188.pdf (Preprint), 10MB
Name:
arXiv:2009.00188.pdf
Beschreibung:
File downloaded from arXiv at 2020-10-26 10:31
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Cohen-Addad, Vincent1, Autor
Klein, Philip N.1, Autor
Marx, Dániel2, Autor           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Data Structures and Algorithms, cs.DS
 Zusammenfassung: Redistricting is the problem of dividing a state into a number $k$ of
regions, called districts. Voters in each district elect a representative. The
primary criteria are: each district is connected, district populations are
equal (or nearly equal), and districts are "compact". There are multiple
competing definitions of compactness, usually minimizing some quantity.
One measure that has been recently promoted by Duchin and others is number of
cut edges. In redistricting, one is given atomic regions out of which each
district must be built. The populations of the atomic regions are given.
Consider the graph with one vertex per atomic region (with weight equal to the
region's population) and an edge between atomic regions that share a boundary.
A districting plan is a partition of vertices into $k$ parts, each connnected,
of nearly equal weight. The districts are considered compact to the extent that
the plan minimizes the number of edges crossing between different parts.
Consider two problems: find the most compact districting plan, and sample
districting plans under a compactness constraint uniformly at random. Both
problems are NP-hard so we restrict the input graph to have branchwidth at most
$w$. (A planar graph's branchwidth is bounded by its diameter.) If both $k$ and
$w$ are bounded by constants, the problems are solvable in polynomial time.
Assume vertices have weight~1. One would like algorithms whose running times
are of the form $O(f(k,w) n^c)$ for some constant $c$ independent of $k$ and
$w$, in which case the problems are said to be fixed-parameter tractable with
respect to $k$ and $w$). We show that, under a complexity-theoretic assumption,
no such algorithms exist. However, we do give algorithms with running time
$O(c^wn^{k+1})$. Thus if the diameter of the graph is moderately small and the
number of districts is very small, our algorithm is useable.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2020-08-312020
 Publikationsstatus: Online veröffentlicht
 Seiten: 21 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 2009.00188
URI: https://arxiv.org/abs/2009.00188
BibTex Citekey: Cohen-Addad_arXiv2009.00188
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: