The problem of proportional apportionment arises whenever we have a finite supply of $k$ indivisible, identical resource units which we have to distribute across $n$ parties fairly, that is according to the proportional share of publicly known and agreed-upon values $v_1,\ldots,v_n$ (of the sum of these values).
A typical example is the assignment of seats in the US house of representatives according to the population count of the states. The de-facto standard to compute such a division is the class of divisor methods.
In recent literature, there are two algorithms that implement divisor methods:
- one by Cheng and Eppstein has worst-case optimal running time but is relatively complex and causes problems when implemented with inexact floating point arithmetic,
- while the other—described by Pukelsheim— is simple and fast in practice but does not offer worst-case guarantees.
We propose a new algorithm that combines the strengths of both methods. Our algorithm is a generalization of the method we devised for the stick-cutting problem and uses a single call to a selection algorithm after elementary preprocessing.
We also empirically demonstrate that
- the Cheng-Eppstein algorithm is much slower than Pukelsheim’s method,
- there are (somewhat realistic) classes of input, where Pukelsheim’s method indeed needs super-linear time, and
- that our new algorithm is almost as fast as Pukelsheim’s method for most inputs, and significantly faster for inputs the latter struggles with.