Balanced Allocations Export

@inproceedings{azar1999, abstract = {Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1 + o(1)) ln n/ ln ln n balls in it. Suppose instead that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. We show that with high probability, the fullest box contains only ln ln n/ ln 2 +O(1) balls -- exponentially less than before. Furthermore, we show that a similar gap exists in the infinite process, where at each step one ball, chosen uniformly at random, is deleted, and one ball is added in the manner above. We discuss consequences of this and related theorems for dynamic resource allocation, hashing, and on-line load balancing.}, author = {Azar, Yossi and Broder, Andrei Z. and Karlin, Anna R. and Upfal, Eli}, booktitle = {SIAM Journal on Computing}, citeulike-article-id = {5721439}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.7396}, keywords = {allocations, ballsintobins, hashing, probability}, pages = {593--602}, posted-at = {2009-09-04 10:16:00}, priority = {2}, title = {Balanced Allocations}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.7396}, volume = {29}, year = {1994} }

TY - CONF ID - azar1999 L3 - citeulike-article-id:5721439 N2 - Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1 + o(1)) ln n/ ln ln n balls in it. Suppose instead that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. We show that with high probability, the fullest box contains only ln ln n/ ln 2 +O(1) balls -- exponentially less than before. Furthermore, we show that a similar gap exists in the infinite process, where at each step one ball, chosen uniformly at random, is deleted, and one ball is added in the manner above. We discuss consequences of this and related theorems for dynamic resource allocation, hashing, and on-line load balancing. EP - 602 TI - Balanced Allocations VL - 29 T2 - SIAM Journal on Computing SP - 593 KW - allocations KW - ballsintobins KW - hashing KW - probability AU - Azar, Yossi AU - Broder, Andrei AU - Karlin, Anna AU - Upfal, Eli PY - 1994/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.7396 ER -