A Doubly Exponentially Crumbled Cake

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125601" target="_blank" >RIV/00216208:11320/12:10125601 - isvavai.cz</a>
Result on the web
<a href="http://www.sciencedirect.com/science/article/pii/S1571065311001132" target="_blank" >http://www.sciencedirect.com/science/article/pii/S1571065311001132</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.endm.2011.09.044" target="_blank" >10.1016/j.endm.2011.09.044</a>

Result language
angličtina
Original language name
A Doubly Exponentially Crumbled Cake
Original language description
We consider the following cake cutting game: Alice chooses a set P of n points in the square (cake) image [0,1]^2, where (0,0) is in P; Bob cuts out n axis-parallel rectangles with disjoint interiors, each of them having a point of P as the lower left corner; Alice keeps the rest. It has been conjectured that Bob can always secure at least half of the cake. This remains unsettled, and it is not even known whether Bob can get any positive fraction independent of n. We prove that if Alice can force Bob?sshare to tend to zero, then she must use very many points; namely, to prevent Bob from gaining more than 1/r of the cake, she needs at least 2^{2^Omega(r)} points.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)