Reitzig, Raphael and Wild, Sebastian
A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment
ArXiv e-prints, 2015
Proportional apportionment is the problem of assigning seats to parties according to their relative share of votes. Divisor methods are the de-facto standard solution, used in many countries.
In recent literature, there are two algorithms that implement divisor methods: one by Cheng and Eppstein (ISAAC, 2014) has worst-case optimal running time but is complex, while the other (Pukelsheim, 2014) is relatively simple and fast in practice but does not offer worst-case guarantees.
We demonstrate that the former algorithm is much slower than the other in practice propose a novel algorithm that avoids the shortcomings of both. We investigate the running-time behavior of the three contenders in order to determine which is most useful in practice.
– arXiv – talk – code –
We thank Chao Xu for pointing us towards the work by Cheng and Eppstein and noting that the problem of envy-free stick-division is related to proportional apportionment as discussed there. He also observed that our approach for cutting sticks – the core ideas of which turned out to carry over to this article – could be improved to run in linear time.
Furthermore, we owe thanks to an anonymous reviewer whose constructive feedback sparked broad changes which have greatly improved the article over its first incarnation.