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 language | English |
|---|---|
| Title of host publication | Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2002) |
| Place of Publication | New York, USA |
| Publisher | ACM Press |
| Pages | 263-264 |
| ISBN (Print) | 0-89871-513-X |
| Publication status | Published - 2002 |
| Event | 13th Annual ACM-SIAM Symposium on Discrete Algortihms, SODA 2002 - Radisson Miyako Hotel, San Francisco, United States Duration: 6 Jan 2002 → 8 Jan 2002 Conference number: 13 https://archive.siam.org/meetings/da02/ |
Conference
| Conference | 13th Annual ACM-SIAM Symposium on Discrete Algortihms, SODA 2002 |
|---|---|
| Abbreviated title | SODA 2002 |
| Country | United States |
| City | San Francisco |
| Period | 6/01/02 → 8/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.