학술논문
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
ISSN
14320541
Abstract
Summary: ``Given a set of $n$ sticks of various (not necessarilydifferent) lengths, what is the largest length so that we can cut $k$equally long pieces of this length from the given set of sticks? Weanalyze the structure of this problem and show that it essentiallyreduces to a single call of a selection algorithm; we thus obtain anoptimal linear-time algorithm. This algorithm also solves the relatedenvy-free stick-division problem, which Segal-Halevi et al. (ACM TransAlgorithms 13(1):1--32, 2016. ISSN: 15496325.https://doi.org/10.1145/2988232) [MR3598117] recently used astheir centralprimitive operation for the first discrete and bounded envy-free cakecutting protocol with a proportionality guarantee when pieces can beput to waste.''