A Simple and Fast Linear-Time Algorithm for Divisor Methods of Apportionment

This article is part of the special issue of *Mathematical Programming B*
commemorating Michel L. Balinksi.

## 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

There are two algorithms that implement divisor methods efficiently:

- one by Cheng and Eppstein has worst-case optimal running time but is relatively complex and (as we observe) 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 a linear-time worst-case guarantee.

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

A full-length technical report with more detailed proofs and further experiments is available here.