Balanced Allocation: Patience is not a Virtue

John Augustine, William K. Moses, Amanda Redlich +1

Load balancing is a well-studied problem, with balls-in-bins being the primary framework. The greedy algorithm $\mathsf{Greedy}[d]$ of Azar et al. places each ball by probing $d >…