All Publications

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

Nov 2017 (Written: Apr 2016)

Raphael Reitzig, Sebastian Wild:

Algorithmica 80, 11, pp 3365-3396 (Nov 2018)

| read herepublisher PDFPDFDOI arXiv |

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:

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.