A lower bound for cake cutting

Jirí Sgall; Gerhard J. Woeginger

doi:10.1007/978-3-540-39658-1_42

A lower bound for cake cutting

Jirí Sgall, Gerhard J. Woeginger

Discrete Mathematics and Mathematical Programming

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

11 Citations (Scopus)

15 Downloads (Pure)

Abstract

We prove that in a certain cake cutting model, every fair cake division protocol for n players must use Ω(n log n) cuts in the worst case. Up to a small constant factor, our lower bound matches a corresponding upper bound in the same model by Even & Paz from 1984.

Original language	English
Title of host publication	Algorithms - ESA 2003
Subtitle of host publication	11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings
Editors	Giuseppe Di Battista, Uri Zwick
Publisher	Springer
Pages	459-469
ISBN (Electronic)	978-3-540-39658-1
ISBN (Print)	978-3-540-20064-2
DOIs	https://doi.org/10.1007/978-3-540-39658-1_42
Publication status	Published - 2003
Event	11th Annual European Symposium on Algorithms, ESA 2003 - Budapest, Hungary Duration: 16 Sept 2003 → 19 Sept 2003 Conference number: 11

Publication series

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

Conference

Conference	11th Annual European Symposium on Algorithms, ESA 2003
Abbreviated title	ESA
Country/Territory	Hungary
City	Budapest
Period	16/09/03 → 19/09/03

Keywords

METIS-213363

Access to Document

10.1007/978-3-540-39658-1_42

Cite this

@inproceedings{4467e57a671642fd8ccd87624bfdda33,

title = "A lower bound for cake cutting",

abstract = "We prove that in a certain cake cutting model, every fair cake division protocol for n players must use Ω(n log n) cuts in the worst case. Up to a small constant factor, our lower bound matches a corresponding upper bound in the same model by Even \& Paz from 1984.",

keywords = "METIS-213363",

author = "Jir{\'i} Sgall and Woeginger, \{Gerhard J.\}",

year = "2003",

doi = "10.1007/978-3-540-39658-1\_42",

language = "English",

isbn = "978-3-540-20064-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "459--469",

editor = "\{Di Battista\}, Giuseppe and Uri Zwick",

booktitle = "Algorithms - ESA 2003",

address = "Germany",

note = "11th Annual European Symposium on Algorithms, ESA 2003, ESA ; Conference date: 16-09-2003 Through 19-09-2003",

}

Sgall, J & Woeginger, GJ 2003, A lower bound for cake cutting. in G Di Battista & U Zwick (eds), Algorithms - ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings. Lecture Notes in Computer Science, vol. 2832, Springer, pp. 459-469, 11th Annual European Symposium on Algorithms, ESA 2003, Budapest, Hungary, 16/09/03. https://doi.org/10.1007/978-3-540-39658-1_42

A lower bound for cake cutting. / Sgall, Jirí; Woeginger, Gerhard J.
Algorithms - ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings. ed. / Giuseppe Di Battista; Uri Zwick. Springer, 2003. p. 459-469 (Lecture Notes in Computer Science; Vol. 2832).

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

TY - GEN

T1 - A lower bound for cake cutting

AU - Sgall, Jirí

AU - Woeginger, Gerhard J.

N1 - Conference code: 11

PY - 2003

Y1 - 2003

N2 - We prove that in a certain cake cutting model, every fair cake division protocol for n players must use Ω(n log n) cuts in the worst case. Up to a small constant factor, our lower bound matches a corresponding upper bound in the same model by Even & Paz from 1984.

AB - We prove that in a certain cake cutting model, every fair cake division protocol for n players must use Ω(n log n) cuts in the worst case. Up to a small constant factor, our lower bound matches a corresponding upper bound in the same model by Even & Paz from 1984.

KW - METIS-213363

U2 - 10.1007/978-3-540-39658-1_42

DO - 10.1007/978-3-540-39658-1_42

M3 - Conference contribution

SN - 978-3-540-20064-2

T3 - Lecture Notes in Computer Science

SP - 459

EP - 469

BT - Algorithms - ESA 2003

A2 - Di Battista, Giuseppe

A2 - Zwick, Uri

PB - Springer

T2 - 11th Annual European Symposium on Algorithms, ESA 2003

Y2 - 16 September 2003 through 19 September 2003

ER -

A lower bound for cake cutting

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this