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



Reitzig, Raphael and Wild, Sebastian ORCID: 0000-0002-6061-9177
(2018) Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks. Algorithmica: an international journal in computer science, 80 (11). pp. 3365-3396.

[thumbnail of reitzig-wild-2018.pdf] Text
reitzig-wild-2018.pdf - Author Accepted Manuscript

Download (759kB) | Preview

Abstract

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) 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.

Item Type: Article
Additional Information: v3 adds more context about the problem
Uncontrolled Keywords: Envy-free stick division, Envy-free allocations, Fair division, Building fences, Stick cutting, Cake cutting with waste, proportional apportionment
Depositing User: Symplectic Admin
Date Deposited: 21 Oct 2019 15:03
Last Modified: 19 Jan 2023 00:21
DOI: 10.1007/s00453-017-0392-3
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3058950