日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細


公開

成果報告書

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

MPS-Authors
/persons/resource/persons250066

Marx,  Dániel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
There are no locators available
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
フルテキスト (公開)

arXiv:2009.00188.pdf
(プレプリント), 10MB

付随資料 (公開)
There is no public supplementary material available
引用

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.


引用: https://hdl.handle.net/21.11116/0000-0007-495A-3
要旨
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.