Multiple-Choice Allocations with Fixed Densities
Ebrahim Malalla · 2008
We analyze the performance of the randomized multiple- choice allocation process in the fixed density model. We show that the allocation process leads to O(log log n) expected maximal bin load when Theta(n) balls are allocated into n bins, where each ball is inserted into the less loaded bin among two bins chosen independently and according to two fixed but possibly different bounded probability densities. Other results are presented.