A lower bound for cake cutting

J. Sgall, G.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 O(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 publicationProceedings of the 11th Annual European Symposium on Algorithms (ESA'2003, Budapest, Hungary, September 16-19, 2003)
EditorsG. Di Battista, U. Zwick
Place of PublicationBerlin
PublisherSpringer
Pages459-469
ISBN (Print)3-540-20064-9
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
Volume2832
ISSN (Print)0302-9743

Cite this

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