分区平面图算法
通过引入一族良好动机的距离度量方法,我们提出了一种寻找最具代表性的选区地图的新方法,在绘制选区地图时实现良好的方法。我们展示了一种可伸缩的、线性时间算法,并推导了样本复杂度保证。我们发现这种方法的一个副产品是能够检测到选区中的区块操纵地图,因为它们在距离方面的 “离群值映射” 中被发现。
Mar, 2022
审计选区规划中的一个有说服力的方法是将该方案与一组中立绘制的选区计划进行比较,这些集合是通过在平衡的图分割上采样分布的算法生成的。我们生成了一种多尺度并行退火方法,在每个尺度上进行局部移动,该方法允许采用多种基于政策的衡量标准。我们在康涅狄格州进行了实证研究,并成功在前所未有的尺度上对尚未采样的基于政策的分布进行快速混合。我们的算法显示出扩展到更广泛的衡量标准的潜力,这将 (i) 允许更有原则性和情境基础的比较,并 (ii) 探索政策对选区划分的典型党派影响。
Jan, 2024
本文研究了三种投票方案的胜者问题和排名问题的复杂度,发现 Young 的方案和 Lewis Carroll 的方案都是 NP 难问题,而 Fishburn 的方案可以通过线性规划高效求解。
Dec, 2001
在平面图情况下,我们证明了与各种满足性、图形和组合问题相关的计数问题的 #P 难度。另外,当局限于计划实例时,我们证明了具有不明确解决方案性的满足性问题的 NP 完全性和与唯一满足性问题相关的随机多项式可简化的 DP 完全性。假设 P≠NP,则以上结果的一个推论是:不存在 ε- 逼近算法,用于在整数上计划线性不等式约束系统的最大化或最小化线性目标函数问题。
Sep, 1998
本文探讨了 k-Balanced Partitioning 问题的两类近似算法:快速但准确度不高和保证高质量准确度但速度较慢的算法。研究表明,这种运行时间和解决方案质量之间的权衡是必要的。我们还提出了一种基于图形类别的规约框架,以证明了该问题的困难性。本文是该问题的第一次双层次不可近似结果。
Nov, 2011
证明了所有有限平面图的 Weisfeiler-Leman (WL) 维度至多为 3,并使用至多 4 个变量的一阶逻辑可定义每个有限平面图。通过分类讨论得出 3 联通平面图的分类,并证明了 3 维 WL 算法可以确定 3 联通平面图的轨道。
Aug, 2017
考察了两种完全比例代表制方法,试图发掘是否可以找到方案和选民组合使得这些问题有高效解法,同时研究了两种规则的参数复杂度,结果表明大多数问题都有多项式时间算法,但单峰选民组合下的 Monroe 规则仍是 NP 难问题。
Feb, 2014
本文研究单交叉选举中的获胜者确定复杂度,在 Chamberlin-Courant 的规则和 Monroe 的规则下,对于宽度有边界的单交叉选举,我们提供了一个多项式时间算法,但 Monroe 的规则仍然是 NP 难问题。在考虑了满足额外约束条件的单交叉选举(每个候选人至少被一个选民排在第一位的选举),我们为 Monroe 的平等版本提供了一个高效的算法。
Jul, 2013