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.
翻译:我们对典型的Camberlin-Courant多赢者投票规则(CC)提出了一种几乎最理想的算法。 在单点优惠剖面上,我们为CCC展示了一种多点时间算法,其中给定的候选人排量设定了$D$的对数大小。实际上,我们的算法运行在2 ⁇ D ⁇ \\cdot 聚(n,m)美元的时间和权力基础上,在“强烈的博览时间假话”下无法改进。我们还将这些结果调整到所有非一致的Thiele规则中,这些规则将CC与批准票普遍化。