Output details
11 - Computer Science and Informatics
University of Liverpool
Article title
Algorithmic Solutions for Envy-Free Cake Cutting
Type
D - Journal article
Title of journal
Operations Research
Article number
-
Volume number
60
Issue number
6
First page of article
1461
ISSN of journal
1526-5463
Year of publication
2012
URL
-
Number of additional authors
2
Additional information
<12>This paper provides algorithmic and complexity-theoretic results for (approximate) envy-free cake cutting. It provides a tight analysis of the classic protocol of Stromquist (1980), and a provably good approximation algorithm for a natural special case. It also provides matching lower and upper bounds for approximate envy-freeness in the oracle-function model. This result implies the previously best-known lower bound of Stromquist (2008) for exact envy-freeness, as highlighted in the recent surveys by Procaccia in CACM 2013 ("Cake Cutting Is Not Childs Play") and the Handbook of Computational Social Choice (forthcoming, preprint available).
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
1
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
