학술논문
Building fences straight and high: an optimal algorithm for finding the maximum length you can cut $k$ times from given sticks.
Document Type
Journal
Author
Reitzig, Raphael (D-RPTU) AMS Author Profile; Wild, Sebastian (3-WTRL-SC) AMS Author Profile
Source
Subject
91 Game theory, economics, social and behavioral sciences -- 91B Mathematical economics
91B32Resource and cost allocation
91B32
Language
English
Abstract
Summary: ``Given a set of $n$ sticks of various (not necessarily different) lengths, what is the largest length so that we can cut $k$ equally long pieces of this length from the given set of sticks? 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. This algorithm also solves the related envy-free stick-division problem, which Segal-Halevi et al. (ACM Trans Algorithms 13(1):1--32, 2016. ISSN: 15496325. https://doi.org/10.1145/2988232) [MR3598117] recently used as their central primitive operation for the first discrete and bounded envy-free cake cutting protocol with a proportionality guarantee when pieces can be put to waste.''