A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment



Reitzig, Raphael and Wild, Sebastian ORCID: 0000-0002-6061-9177
(2015) A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment. [Report]

[thumbnail of 1504.06475v4.pdf] Text
1504.06475v4.pdf - Submitted version

Download (2MB) | Preview

Abstract

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 and 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.

Item Type: Report
Additional Information: (v4 adds missing figures in v3)
Uncontrolled Keywords: cs.DS, cs.DS
Depositing User: Symplectic Admin
Date Deposited: 15 Aug 2019 14:37
Last Modified: 19 Jan 2023 00:29
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3051853