A generalization of multiple choice balls-into-bins
Gahyun Park · 2011
In the multiple choice balls into bins problem, each ball is placed into the least loaded one out of d bins chosen independently and uniformly at random (i.u.r.}). It is known that the maximum load after n balls are placed into n bins is ln ln n/ln d + O(1).