論文の概要: Optimizing Districting Plans to Maximize Majority-Minority Districts via IPs and Local Search
- arxiv url: http://arxiv.org/abs/2508.07446v1
- Date: Sun, 10 Aug 2025 17:58:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-12 21:23:28.860061
- Title: Optimizing Districting Plans to Maximize Majority-Minority Districts via IPs and Local Search
- Title（参考訳）: マイノリティ地区のIPとローカルサーチによる最大化のための地区計画の最適化
- Authors: Daniel Brous, David Shmoys,
- Abstract要約: 訴訟の再制限において、投票権法(英語版)の施行は、しばしば、現行の提案よりも多数派マイノリティ地区を多数示す地区計画を裁判所に提供することに関与している。
本稿では,複数データセット上の短いバーストを性能的に上回る整数型プログラミングを用いて,多数のマイノリティ領域を持つ州全体の計画を生成する階層列生成アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In redistricting litigation, effective enforcement of the Voting Rights Act has often involved providing the court with districting plans that display a larger number of majority-minority districts than the current proposal (as was true, for example, in what followed Allen v. Milligan concerning the congressional districting plan for Alabama in 2023). Recent work by Cannon et al. proposed a heuristic algorithm for generating plans to optimize majority-minority districts, which they called short bursts; that algorithm relies on a sophisticated random walk over the space of all plans, transitioning in bursts, where the initial plan for each burst is the most successful plan from the previous burst. We propose a method based on integer programming, where we build upon another previous work, the stochastic hierarchical partitioning algorithm, which heuristically generates a robust set of potential districts (viewed as columns in a standard set partitioning formulation); that approach was designed to optimize a different notion of fairness across a statewide plan. We design a new column generation algorithm to find plans via integer programming that outperforms short bursts on multiple data sets in generating statewide plans with significantly more majority-minority districts. These results also rely on a new local re-optimization algorithm to iteratively improve on any baseline solution, as well as an algorithm to increase the compactness of districts in plans generated (without impacting the number of majority-minority districts).
- Abstract（参考訳）: 訴訟の再制限において、投票権法(英語版)の施行は、しばしば裁判所に、現在の提案よりも多数派マイノリティ地区(例えば2023年のアラバマ州議会選挙区計画に関するアレン対ミリガン事件(英語版))を示す地区計画を提供することに関係している。
Cannonらによる最近の研究は、多数派マイノリティ地区を最適化する計画を生成するためのヒューリスティックアルゴリズムを提案しており、これは短いバーストと呼ばれ、このアルゴリズムは全てのプランの空間を高度にランダムに歩き、バーストに遷移し、各バーストの初期計画が以前のバーストから最も成功した計画である。
提案手法は,確率的階層的分割アルゴリズム(Standard set partitioning formulation のコラムとみなす)をヒューリスティックに生成する手法であり,この手法は,州全体の計画における公平性の異なる概念を最適化するために設計されている。
我々は,複数データセットの短いバーストを上回り,多数派マイノリティ地区をはるかに多く含む州全体の計画を生成するために,整数計画を用いた新しいカラム生成アルゴリズムを設計する。
これらの結果は、任意のベースライン解を反復的に改善するための新しい局所的な再最適化アルゴリズムや、(多数派マイノリティ地区の数に影響を与えずに)生成された計画における地区のコンパクト性を高めるアルゴリズムにも依存している。
関連論文リスト
- Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
提案するSEQUOIAは,動作空間に対する長期報酬を直接最適化するRLアルゴリズムである。
我々は,複数介入,経路制約,二部間マッチング,容量制約という,制約を伴う4つの新しいレスレス・バンディット問題に対して,SEQUOIAを実証的に検証した。
論文 参考訳（メタデータ） (2025-03-01T21:25:21Z) - Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans [1.1233768932957773]
説得力のある方法は、計画と中立に描画された再限定計画のアンサンブルを比較することである。
アンサンブルと所定の計画との党派差を監査するためには、非党派基準が一致していることを保証する必要がある。
本研究では,各スケールで局所移動を行うマルチスケール並列テンパリング手法を提案する。
論文 参考訳（メタデータ） (2024-01-30T21:33:05Z) - Simple Opinion Dynamics for No-Regret Learning [38.61048016579232]
分散GOSSIPモデルにおける協調的マルチエージェントバンディット設定について検討する。
この設定のために、メモリレスおよび時間に依存しないプロトコルのファミリーを導入・分析する。
定常的な報酬設定のために、これらの単純なプロトコルが世界の最高の振る舞いを示すことを初めて証明する。
論文 参考訳（メタデータ） (2023-06-14T17:59:15Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Fairmandering: A column generation heuristic for fairness-optimized
political districting [0.0]
アメリカの当選者全選挙区制は、政治家に選挙区境界を操作することで選挙結果を作る権限を与えている。
既存の計算ソリューションは主に、政治的、人口統計学的入力を無視して、偏見のない地図を描くことに集中し、代わりに単にコンパクト性のために最適化する。
コンパクトさと公正さは品質であるので、これは欠点のあるアプローチであり、公正性の任意の片方向線形定義を明示的に最適化するスケーラブルな2段階法を導入する。
論文 参考訳（メタデータ） (2021-03-21T19:22:42Z) - Compactness statistics for spanning tree recombination [0.0]
レコム法は、他の方法よりもコンパクトな地区で計画を作成する。
2つの格子グラフとボルダー郡管区グラフの2分割計画のアンサンブルを構築した。
これはReCom法による分割計画のコンパクト性を理解するための重要なステップである。
論文 参考訳（メタデータ） (2021-03-03T21:39:51Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - Sequential Monte Carlo for Sampling Balanced and Compact Redistricting
Plans [0.0]
本稿では,現実的な目標分布に収束する再限定計画のサンプルを生成する,SMC(Sequential Monte Carlo)アルゴリズムを提案する。
提案アルゴリズムの精度を,すべての再分割計画を列挙可能な小さなマップを用いて検証する。
次に、SMCアルゴリズムを用いて、ペンシルベニア州の最近の有名な再分権事件において、関係当事者が提出したいくつかの地図のパルチザン的含意を評価する。
論文 参考訳（メタデータ） (2020-08-13T23:26:34Z) - Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
暗黙的な逐次計画の仮定に代わるものを検討する。
本稿では,最適計画の近似を行うため,Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS)を提案する。
計画順序に対するこのアルゴリズム的柔軟性は,グリッドワールドにおけるナビゲーションタスクの改善に繋がることを示す。
論文 参考訳（メタデータ） (2020-04-23T18:08:58Z) - Decentralized MCTS via Learned Teammate Models [89.24858306636816]
本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。
深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
論文 参考訳（メタデータ） (2020-03-19T13:10:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。