A lower bound for cake cutting

J. Sgall, G.J. Woeginger

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

11 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