論文の概要: Gerrymandering Planar Graphs
- arxiv url: http://arxiv.org/abs/2312.14721v2
- Date: Mon, 8 Jan 2024 01:10:44 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-09 21:48:10.132877
- Title: Gerrymandering Planar Graphs
- Title（参考訳）: gerrymandering平面グラフ
- Authors: Jack Dippel, Max Dupr\'e la Tour, April Niu, Sanjukta Roy, Adrian
Vetta
- Abstract要約: 再限定問題(発芽)の計算複雑性について検討する。
我々は、ジェリーマンダリング問題は、$lambda$-outerplanar graphsで時間内に解決可能であることを証明した。
- 参考スコア（独自算出の注目度）: 1.237454174824584
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the computational complexity of the map redistricting problem
(gerrymandering). Mathematically, the electoral district designer
(gerrymanderer) attempts to partition a weighted graph into $k$ connected
components (districts) such that its candidate (party) wins as many districts
as possible. Prior work has principally concerned the special cases where the
graph is a path or a tree. Our focus concerns the realistic case where the
graph is planar. We prove that the gerrymandering problem is solvable in
polynomial time in $\lambda$-outerplanar graphs, when the number of candidates
and $\lambda$ are constants and the vertex weights (voting weights) are
polynomially bounded. In contrast, the problem is NP-complete in general planar
graphs even with just two candidates. This motivates the study of approximation
algorithms for gerrymandering planar graphs. However, when the number of
candidates is large, we prove it is hard to distinguish between instances where
the gerrymanderer cannot win a single district and instances where the
gerrymanderer can win at least one district. This immediately implies that the
redistricting problem is inapproximable in polynomial time in planar graphs,
unless P=NP. This conclusion appears terminal for the design of good
approximation algorithms -- but it is not. The inapproximability bound can be
circumvented as it only applies when the maximum number of districts the
gerrymanderer can win is extremely small, say one. Indeed, for a fixed number
of candidates, our main result is that there is a constant factor approximation
algorithm for redistricting unweighted planar graphs, provided the optimal
value is a large enough constant.
- Abstract（参考訳）: 地図再帰問題 (gerrymandering) の計算複雑性について検討する。
数学的には、選挙地区設計者 (gerrymanderer) は、重み付きグラフを$k$連結成分 (districts) に分割し、その候補 (party) ができるだけ多くの地区で勝利する。
先行研究は主に、グラフがパスまたはツリーである特別なケースに関するものである。
私たちの焦点は、グラフが平面である現実的なケースに関するものです。
我々は、候補数と$\lambda$が定数であり、頂点重み(投票重み)が多項式有界であるとき、ジェリーマンディング問題は$\lambda$-outerplanar graphsの多項式時間で解けることを証明した。
対照的に、問題は2つの候補でさえ一般平面グラフにおいてNP完全である。
これは、gerrymandering平面グラフの近似アルゴリズムの研究を動機付ける。
しかし、候補数が大きければ、ゲリーマンデラーが1つの地区に勝てない場合と、ゲリーマンデラーが少なくとも1つの地区に勝てる場合とを区別することは困難である。
これは即時、 P=NP でない限り、再制限問題は平面グラフの多項式時間では適用できないことを意味する。
この結論は、優れた近似アルゴリズムの設計のターミナルであるように見えるが、そうではない。
ゲリーマンデラーが勝つことができる範囲の最大数が極端に小さい場合にのみ適用されるため、近似可能性の境界は回避できる。
実際、固定数の候補に対して、我々の主な結果は、最適値が十分大きな定数であれば、未重み付き平面グラフを再配置するための定数係数近似アルゴリズムが存在することである。
関連論文リスト
- Don't Trust A Single Gerrymandering Metric [0.0]
これらの指標のそれぞれが,ゲーリーマンダリングを検出するために,単一の孤立量として使用する場合,ゲーム可能であることを示す。
我々は,山登り法を用いて,メートル法上の境界に制約された地区計画を生成するとともに,当事者が獲得した地区数を最大又はほぼ最大化する。
これらの結果の明らかな結果の1つは、ゲーリーマンダリングを避けるために、再分権委員会が満たさなければならないメートル法上の事前境界を指定することの事実を示すことである。
論文 参考訳（メタデータ） (2024-09-25T02:40:09Z) - Drawing Competitive Districts in Redistricting [1.5654305985353367]
我々は、少なくとも一定数の競争地区で計画を描く問題について論じる。
競争地区での計画作成の課題は、非常に自然な例であってもNPハードであることが示される。
簡単な登山手順では、すべての地区が競争力のある現実の州で地区を見つけることができることを示す。
論文 参考訳（メタデータ） (2024-04-17T00:09:41Z) - A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near
Neighbor Graph [51.880164098926166]
グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。
グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。
低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
論文 参考訳（メタデータ） (2023-03-10T21:18:34Z) - Predicting Winning Regions in Parity Games via Graph Neural Networks
(Extended Abstract) [68.8204255655161]
グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。
これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
論文 参考訳（メタデータ） (2022-10-18T15:10:25Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - Expected Frequency Matrices of Elections: Computation, Geometry, and
Preference Learning [58.23459346724491]
我々は、Szufa et al.(AAMAS 2020)の「選挙マップ」アプローチを用いて、よく知られた投票分布を分析します。
分布の「スケルトン写像」を描き、その頑健さを評価し、その性質を分析する。
論文 参考訳（メタデータ） (2022-05-16T17:40:22Z) - Mathematically Quantifying Non-responsiveness of the 2021 Georgia
Congressional Districting Plan [3.097163558730473]
並列テンパリング法とReComを併用したメトロポリケートサンプリング手法を応用した。
ジョージア州における地区計画の最初の事例研究を通じて、これらの改善を開拓する。
我々の分析では、ジョージア州の選挙は、この制定された計画の下で、確実に9人の共和党員と5人の民主党員を選出すると予想している。
論文 参考訳（メタデータ） (2022-03-13T02:58:32Z) - Implications of Distance over Redistricting Maps: Central and Outlier
Maps [6.757783454836096]
代表制民主主義では、選挙区を代表を選出する選挙区の集合に分割するために、再分権地図が選択される。
有効な再限定写像は、コンパクトで連続であり、ほぼ同じ人口であるような制約の集合を満たさなければならない。
この事実は地図の再区画化の難しさを招き、党派議会が不公平に好む地図を選ぶことで、おそらくはゲリマンダーにすることができる。
論文 参考訳（メタデータ） (2022-03-02T04:59:30Z) - Fairmandering: A column generation heuristic for fairness-optimized
political districting [0.0]
アメリカの当選者全選挙区制は、政治家に選挙区境界を操作することで選挙結果を作る権限を与えている。
既存の計算ソリューションは主に、政治的、人口統計学的入力を無視して、偏見のない地図を描くことに集中し、代わりに単にコンパクト性のために最適化する。
コンパクトさと公正さは品質であるので、これは欠点のあるアプローチであり、公正性の任意の片方向線形定義を明示的に最適化するスケーラブルな2段階法を導入する。
論文 参考訳（メタデータ） (2021-03-21T19:22:42Z) - Social Distancing is Good for Points too! [91.3755431537592]
点が近すぎるとFCNNの動作が悪くなることを示す。
そして、そのようなケースを避けるためにアルゴリズムの修正に成功した。
この修正はアルゴリズムの近似保証とともに有用な上界を証明するのに十分である。
論文 参考訳（メタデータ） (2020-06-28T16:49:59Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。