An approximation scheme for cake division with a linear number of cuts

J. Sgall, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
1 Downloads (Pure)

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 prove the following result: For every e>0, there exists a cake division scheme for n players that uses at most cen cuts, and in which each player can enforce to get a share of at least (1-e)/n of the cake according to his own private measure.
Original languageEnglish
Pages (from-to)205-211
JournalCombinatorica
Volume27
Issue number2
DOIs
Publication statusPublished - 2007

Fingerprint

Dive into the research topics of 'An approximation scheme for cake division with a linear number of cuts'. Together they form a unique fingerprint.

Cite this