Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks

The Stick-Cutting Problem

Assume you have a supply of $n$ sticks of various lengths, say $L_1,\ldots,L_n$, and you need $k$ equally long pieces (as legs for a table; as posts for a fence; as boards for a shelf…).

What is the maximal length of the pieces you can get from these (without using glue)?

The problem is also called envy-free stick-division problem since—if we interpret the length of a stick as its value—cutting sticks as above ensures that we can produce $k$ maximal pieces that we can assign to $k$ players without inducing envy between them.

Origins and Applications

This elementary problem has various connections to other problems:

• envy-free cake cutting, see the stackexchange question that originally got us interested in the problem,
• the problem of proportional apportionment,
• and it appeared in a programming contest, and
• it is essentially a special case of the problem of selection from the (multiset-)union of sorted sequences. The Frederickson-Johnson algorithm solves the general problem optimally, but can be improved to linear time for the special sorted subsequences arising in the stick-cutting problem

Our Contribution

We analyze the structure of this problem and show that it essentially reduces to a single call of a selection algorithm; we thus obtain an optimal linear-time algorithm.

The core idea is to compute cheap upper and lower bounds for the cut length $l^\star$ of the $k$ pieces that we eventually use. This allows to reduce the set of lengths that we have to consider to $O(n)$ candidates. Using arguments of Cheng & Eppstein from an algorithm for the apportionment problem, we can find our optimal cut length $l^*$ by selecting the $k$th largest cut-length candidate.

Despite the simplicity of our algorithm, it did not seem to be known before.