论文标题
关于重新划分的地理聚类问题的计算障碍性
On the computational tractability of a geographic clustering problem arising in redistricting
论文作者
论文摘要
重新分配是将一个国家分为数字$ k $的地区的问题，称为地区。每个地区的选民选举代表。主要标准是：每个地区都连接，地区人口相等（或几乎相等），并且地区“紧凑”。紧凑性有多种竞争的定义，通常使一些数量最小化。 杜钦（Duchin）最近促进的一种措施是切割边缘的数量。在重新划分的情况下，必须将一个原子区域提供给每个地区。给出了原子区域的种群。考虑每个原子区域一个顶点（重量等于该地区人口）的图形和共有边界的原子区域之间的边缘。区域计划是将顶点分为$ K $零件的，每个零件几乎相等。该地区被认为是紧凑的，以至于计划将不同部分之间的边缘交叉数量最小化。 考虑两个问题：找到最紧凑的区域计划，并随机统一地在紧凑的约束下进行样本区域计划。这两个问题都是NP-固定的，因此我们将输入图限制为最多$ W $。 （平面图的分支在其直径的界定。）如果$ k $和$ w $均受常数界限，则可以在多项式时间内解决问题。假设顶点的重量〜1。人们想要对某些常数$ c $ $ o（f（k，w）n^c）的运行时间的算法，对于某些常数$ c $，独立于$ k $和$ w $，在这种情况下，这些问题据说相对于$ k $和$ w $是固定参数可触及的）。我们表明，在复杂性理论假设下，不存在这种算法。但是，我们确实提供了运行时间$ O（c^wn^{k+1}）$的算法。因此，如果图的直径适中较小，并且地区的数量很少，则我们的算法是可用的。
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.
