2013/12/31 by Amanda Redlich, Redlich, Amanda
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Search Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1401.0223
openalex publication_date 2013/12/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the unbalanced allocation of m balls into n bins by a randomized algorithm using the "power of two choices". For each ball, we select a set of bins at random, then place the ball in the fullest bin within the set. Applications of this generic algorithm range from cost minimization to condensed matter physics. In this paper, we analyze the distribution of the bin loads produced by this algorithm, considering, for example, largest and smallest loads, loads of subsets of the bins, and the likelihood of bins having equal loads.