An Approximation Scheme For Cake Division With A Linear Number Of Cuts

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 ε>0, there exists a cake division scheme for n players that uses at most c_εn cuts, and in which each player can enforce to get a share of at least (1-ε)/n of the cake according to his own private measure. * Partially supported by Institute for Theoretical Computer Science, Prague (project LN00A056 of MŠMT ČR) and grant IAA1019401 of GA AV ČR.