The (1 + beta)-Choice Process and Weighted Balls-into-Bins

Yuval Peres, Kunal Talwar, Udi WiederSODA 2010 · OpenReview

Abstract

Suppose m balls are sequentially thrown into n bins where each ball goes into a random bin. It is well-known that the gap between the load of the most loaded bin and the average is , or large m. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to Θ(log log n) independent of m. Consider now the following “(1 + β)-choice” process for some parameter β ∊ (0, 1): each ball goes to a random bin with probability (1 – β) and the lesser loaded of two random bins with probability β. How does the gap for such a process behave? Suppose that the weight of each ball was drawn from a geometric distribution. How is the gap (now defined in terms of weight) affected? In this work, we develop general techniques for analyzing such balls-into-bins processes. Specifically, we show that for the (1 + β)-choice process above, the gap is Θ(log n/β), irrespective of m. Moreover the gap stays at Θ(log n/β) in the weighted case for a large class of weight distributions. No non-trivial explicit bounds were previously known in the weighted case, even for the 2-choice paradigm.
BibTeX
@inproceedings{peres2010beta,
  author = {Yuval Peres and Kunal Talwar and Udi Wieder},
  title = {{The (1 + beta)-Choice Process and Weighted Balls-into-Bins}},
  booktitle = {SODA},
  year = {2010},
  url = {https://openreview.net/forum?id=F0KmGPf1rIQ},
}

Loading related content...

Figure