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.

Text
reitzig-wild-2018.pdf - Author Accepted Manuscript
Download (759kB) | Preview

Official URL: https://link.springer.com/article/10.1007/s00453-0...

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:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3058950