An Approximation Scheme for Cake Division with a Linear Number of Cuts

Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

Abstract

In the cake cutting problem, n ≥ 2 playerswanttocuta cake into n pieces so that every player gets a ‘fair’ share of the cake by his own measure. We prove the following result: For every ∈>0, there exists a cake division scheme for n players that uses at most c ∈n cuts, and in which each player can enforce to get a share of at least (1-∈)/nof the cake according to his own private measure.
Original languageEnglish
Title of host publicationAlgorithms — ESA 2002
Subtitle of host publication10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings
EditorsRolf Möhring, Rajeev Raman
Place of PublicationBerlin
PublisherSpringer
Pages896-901
ISBN (Electronic)978-3-540-45749-7
ISBN (Print)978-3-540-44180-9
DOIs
Publication statusPublished - 2002
Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
Duration: 17 Sep 200221 Sep 2002
Conference number: 10

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2461
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th Annual European Symposium on Algorithms, ESA 2002
Abbreviated titleESA
CountryItaly
CityRome
Period17/09/0221/09/02

Keywords

  • METIS-208660

Fingerprint Dive into the research topics of 'An Approximation Scheme for Cake Division with a Linear Number of Cuts'. Together they form a unique fingerprint.

Cite this