Reitzig, Raphael and Wild, Sebastian
Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks
Algorithmica,
2018
Segal-Halevi, Hassidim, and Aumann (AAMAS, 2015) propose the problem of cutting sticks so that at least k sticks have equal length and no other stick is longer. This allows for an envy-free allocation of sticks to k players, one each. The resulting number of sticks should also be minimal.
We analyze the structure of this problem and devise a linear-time algorithm for it.
Erel Segal-Halevi posed the original question on Computer Science Stack Exchange. Our approach is based on observations in the answers by Abhishek Bansal, InstructedA and FrankW. Hence, even though the eventual algorithm and its presentation have been developed and refined offline with the use of a blackboard and lots of paper, the result has been the product of a small “crowd” collaboration made possible by the Stack Exchange platform.
We thank Chao Xu for pointing us towards the work by Cheng and Eppstein (which lead to another article of ours), and for providing the observation we utilize in Section 4.1.