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