An approximation scheme for cake division with a linear number of cuts

G.J. Woeginger

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

An approximation scheme for cake division with a linear number of cuts

G.J. Woeginger

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

5 Citations (Scopus)

Abstract

In the cake cutting problem, n = 2 players want to cut a 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 (Proceedings of the 10th Annual European Symposium, Rome, Italy, September 17-21, 2002)
Place of Publication	Berlin
Publisher	Springer
Pages	896-901
ISBN (Print)	978-3-540-44180-9
DOIs	https://doi.org/10.1007/3-540-45749-6_77
Publication status	Published - 2002

Publication series

Name	Lecture Notes in Computer Science
Volume	2461
ISSN (Print)	0302-9743

Access to Document

10.1007/3-540-45749-6_77

Cite this

@inproceedings{41baa5fc70bf4777baf66c8a0e53a2bf,

title = "An approximation scheme for cake division with a linear number of cuts",

abstract = "In the cake cutting problem, n = 2 players want to cut a 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",

author = "G.J. 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",

booktitle = "Algorithms - ESA 2002 (Proceedings of the 10th Annual European Symposium, Rome, Italy, September 17-21, 2002)",

address = "Germany",

}

An approximation scheme for cake division with a linear number of cuts. / Woeginger, G.J.

Algorithms - ESA 2002 (Proceedings of the 10th Annual European Symposium, Rome, Italy, September 17-21, 2002). 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, G.J.

PY - 2002

Y1 - 2002

N2 - In the cake cutting problem, n = 2 players want to cut a 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 players want to cut a 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

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 (Proceedings of the 10th Annual European Symposium, Rome, Italy, September 17-21, 2002)

PB - Springer

CY - Berlin

ER -