Next: About this document ...
Papers on Cake Cutting I want to read
by William Gasarch
(For now this is just papers that I want to gather in one place)
- Cutting a Cake for Five People
by Saberi and Wang.
Appeared in Fifth Annusal Conference on Algorithmic Aspects in Information and
Management, 2009. Page 292.
Moving Knife Protocol for envy-free for 5 people
ENVYFREE5.PDF
- On the Complexity of Cake cutting by Woeginger and Sgall.
Appeared in Discrete Optimization Vol 4, 2007.
Lower bound Omega(nlog n) on number of cuts for proportional-
but the pieces must be contigous.
WLBPROP.PDF
- Cake cutting is really not a piece of cake
by Edmonds and Pruhs.
ACM Trans. on Alg, 2011.
Earlier version in SODA 2006.
Lower bound Omega(nlog n) on number of cuts for proportional.
Model is reasonable, result is tight.
LBPROP.PDF
- Envy-free cake division cannot be found by finite protocol
By Stromquist.
Appeared in Electronic Journal of Combinatorics Vol 15, 2008.
Lower bound on number of cuts for envyfree - has to be unbounded.
But we insist that the pieces be contigous.
LBENVYFREE.PDF
- Towards More expressive Cake Cutting
by Caragiannis, Lai, Procaccia.
Looks a model where crumbs are worth zero.
EXPRESSIVE.PDF
- How to cut a cake fairly
by Walter Stomquist.
American Math Monthly, 1980.
EXISTSENVYFREE.PDF
- How to cut a cake before the party ends
by Kurokawa, Lai, Procaccia.
If the valuations are piecewise linear this gives
envy free in bounded number of cuts.
envyfreebounded.pdf
- Thou shalt not covet thy neighbors cake.
By Procaccia. Gives quadratic lower bound on envy free
for n people.
LBENVYFREESQ.PDF
- Solution of Peter Winkler's Pizza Problem.
By Cibulka, et al.
From Fete of Combinatorics and Computer Science.
PIZZA.PDF
- A Discrete and Bounded Envy-free Cake cutting Protocol for Four Agents.
By Haris Aziz and Simon McKenzie.
ENVY.PDF
Next: About this document ...
Bill Gasarch
2016-01-27