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

Gerhard Woeginger

doi:10.1007/3-540-45749-6_77

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

Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

6 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 language	English
Title of host publication	Algorithms — ESA 2002
Subtitle of host publication	10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings
Editors	Rolf Möhring, Rajeev Raman
Place of Publication	Berlin
Publisher	Springer
Pages	896-901
ISBN (Electronic)	978-3-540-45749-7
ISBN (Print)	978-3-540-44180-9
DOIs	https://doi.org/10.1007/3-540-45749-6_77
Publication status	Published - 2002
Event	10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy Duration: 17 Sep 2002 → 21 Sep 2002 Conference number: 10

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2461
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th Annual European Symposium on Algorithms, ESA 2002
Abbreviated title	ESA
Country/Territory	Italy
City	Rome
Period	17/09/02 → 21/09/02

Keywords

METIS-208660

Access to Document

10.1007/3-540-45749-6_77

Cite this

@inproceedings{1812db1ac56c452a9aea3c1826c6241d,

title = "An Approximation Scheme for Cake Division with a Linear Number of Cuts",

abstract = "In the cake cutting problem, n ≥ 2 playerswanttocuta cake into n pieces so that every player gets a {\textquoteleft}fair{\textquoteright} 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.",

keywords = "METIS-208660",

author = "Gerhard Woeginger",

year = "2002",

doi = "10.1007/3-540-45749-6_77",

language = "English",

isbn = "978-3-540-44180-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "896--901",

editor = "Rolf M{\"o}hring and Rajeev Raman",

booktitle = "Algorithms — ESA 2002",

note = "10th Annual European Symposium on Algorithms, ESA 2002, ESA ; Conference date: 17-09-2002 Through 21-09-2002",

}

Woeginger, G 2002, An Approximation Scheme for Cake Division with a Linear Number of Cuts. in R Möhring & R Raman (eds), Algorithms — ESA 2002: 10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings. Lecture Notes in Computer Science, vol. 2461, Springer, Berlin, pp. 896-901, 10th Annual European Symposium on Algorithms, ESA 2002, Rome, Italy, 17/09/02. https://doi.org/10.1007/3-540-45749-6_77

An Approximation Scheme for Cake Division with a Linear Number of Cuts. / Woeginger, Gerhard.

Algorithms — ESA 2002: 10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings. ed. / Rolf Möhring; Rajeev Raman. Berlin : Springer, 2002. p. 896-901 (Lecture Notes in Computer Science; Vol. 2461).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Woeginger, Gerhard

N1 - Conference code: 10

PY - 2002

Y1 - 2002

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

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

KW - METIS-208660

U2 - 10.1007/3-540-45749-6_77

DO - 10.1007/3-540-45749-6_77

M3 - Conference contribution

SN - 978-3-540-44180-9

T3 - Lecture Notes in Computer Science

SP - 896

EP - 901

BT - Algorithms — ESA 2002

A2 - Möhring, Rolf

A2 - Raman, Rajeev

PB - Springer

CY - Berlin

T2 - 10th Annual European Symposium on Algorithms, ESA 2002

Y2 - 17 September 2002 through 21 September 2002

ER -