HackerPapers

arXiv:1502.04048cs.DS

Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts

Raphael Reitzig, Sebastian Wild

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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, Hassidim, and Aumann (AAMAS, 2015) 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.

arXiv comments
v3 adds more context about the problem
Journal reference
Reitzig, R. & Wild, S. Algorithmica (2017). https://doi.org/10.1007/s00453-017-0392-3
DOI
doi:10.1007/s00453-017-0392-3
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Dec 2015 to Dec 2015.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Ask HN: Papers you read in 2015? 1 comment

    • Here is an accessible algorithms paper. It's a cute puzzle problem. It was inspired by answers on cs.stackexchange. Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts http://arxiv.org/abs/1502.04048

      chaoxuView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.