论文标题
Chamberlin-Courant和Thiele投票规则的近乎紧密的算法
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules
论文作者
论文摘要
我们为单峰偏好配置文件上经典的Chamberlin-Courant多翼投票规则（CC）提供了一种几乎最佳的算法。鉴于$ n $选民和$ M $候选人，它几乎在输入大小的几乎线性时间内运行，改善了Betzler等人的先前最佳$ O（NM^2）$ TIME算法。 （2013）。我们还根据候选人命中操作研究了几乎单峰偏好概况的多翼投票规则。我们显示了CC的多项式时间算法，其中给定的候选损坏集$ d $具有对数大小。实际上，我们的算法以$ 2^{| d |} \ cdot poly（n，m）$时间运行，并且在强的指数时间假设下无法提高功率的基础。我们还将这些结果调整为所有非恒定的Thiele规则，该规则通过批准选票概括了CC。
We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given $n$ voters and $m$ candidates, it runs in almost linear time in the input size, improving the previous best $O(nm^2)$ time algorithm of Betzler et al. (2013). We also study multiwinner voting rules on nearly single-peaked preference profiles in terms of the candidate-deletion operation. We show a polynomial-time algorithm for CC where a given candidate-deletion set $D$ has logarithmic size. Actually, our algorithm runs in $2^{|D|} \cdot poly(n,m)$ time and the base of the power cannot be improved under the Strong Exponential Time Hypothesis. We also adapt these results to all non-constant Thiele rules which generalize CC with approval ballots.
