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

## Proportional Apportionment

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

## Previous Results

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.

## Our Contribution

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.