A lower bound for cake cutting

Jirí Sgall, Gerhard J. Woeginger

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

9 Citations (Scopus)

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 languageEnglish
Title of host publicationAlgorithms - ESA 2003
Subtitle of host publication11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings
EditorsGiuseppe Di Battista, Uri Zwick
PublisherSpringer
Pages459-469
ISBN (Electronic)978-3-540-39658-1
ISBN (Print)978-3-540-20064-2
DOIs
Publication statusPublished - 2003
Event11th Annual European Symposium  on Algorithms, ESA 2003 - Budapest, Hungary
Duration: 16 Sep 200319 Sep 2003
Conference number: 11

Publication series

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

Conference

Conference11th Annual European Symposium  on Algorithms, ESA 2003
Abbreviated titleESA
CountryHungary
CityBudapest
Period16/09/0319/09/03

Keywords

  • METIS-213363

Cite this

Sgall, J., & Woeginger, G. J. (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 (pp. 459-469). (Lecture Notes in Computer Science; Vol. 2832). Springer. https://doi.org/10.1007/978-3-540-39658-1_42