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.
|Title of host publication||Proceedings of the 11th Annual European Symposium on Algorithms (ESA'2003, Budapest, Hungary, September 16-19, 2003)|
|Editors||G. Di Battista, U. Zwick|
|Place of Publication||Berlin|
|Publication status||Published - 2003|
|Name||Lecture Notes in Computer Science|