How to cut a cake almost fairly

S.O. Krumke, M. Lipmann, W. de Paepe, D. Poensgen, J. Rambau, L. Stougie, Gerhard Woeginger

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

7 Citations (Scopus)

Abstract

In the cake cutting problem, n ≥ 2 players want to cut a cake into n pieces so that every player gets a "fair" share of the cake by his own measure. We describe a protocol with n - 1 cuts in which each player can enforce to get a share of at least 1/(2n - 2) of the cake. Moreover we show that no protocol with n - 1 cuts can guarantee a better fraction.
Original languageEnglish
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2002)
Place of PublicationNew York, USA
PublisherACM Press
Pages263-264
ISBN (Print)0-89871-513-X
Publication statusPublished - 2002
Event13th Annual ACM-SIAM Symposium on Discrete Algortihms, SODA 2002 - Radisson Miyako Hotel, San Francisco, United States
Duration: 6 Jan 20028 Jan 2002
Conference number: 13
https://archive.siam.org/meetings/da02/

Conference

Conference13th Annual ACM-SIAM Symposium on Discrete Algortihms, SODA 2002
Abbreviated titleSODA 2002
CountryUnited States
CitySan Francisco
Period6/01/028/01/02
Internet address

Keywords

  • METIS-208657

Cite this

Krumke, S. O., Lipmann, M., de Paepe, W., Poensgen, D., Rambau, J., Stougie, L., & Woeginger, G. (2002). How to cut a cake almost fairly. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2002) (pp. 263-264). New York, USA: ACM Press.