Title :
Balanced Allocations of Cake
Author :
Edmonds, Jeff ; Pruhs, Kirk
Author_Institution :
Dept. of Comput. Sci. & Eng., York Univ., Toronto, Ont.
Abstract :
We give a randomized algorithm for the well known caking cutting problem that achieves approximate fairness, and has complexity O(n), when all players are honest. The heart of this result involves extending the standard offline multiple-choice balls and bins analysis to the case where the underlying resources/bins/machines have different utilities to different players/balls/jobs
Keywords :
approximation theory; bin packing; computational complexity; game theory; randomised algorithms; bins analysis; caking cutting problem; fair approximation; offline multiple-choice balls analysis; randomized algorithm; Algorithm design and analysis; Books; Computer science; Heart; Kirk field collapse effect; Mathematics; Protocols;
Conference_Titel :
Foundations of Computer Science, 2006. FOCS '06. 47th Annual IEEE Symposium on
Conference_Location :
Berkeley, CA
Print_ISBN :
0-7695-2720-5
DOI :
10.1109/FOCS.2006.17
