Name
Abstract | ||
|---|---|---|
In the classical balls-and-bins setup, n balls are thrown independently and uniformly into n bins. The most loaded bin then has log n/log log n balls with high probability. A famous result of Aztar, Brooder, Karolin and Opal states that, when given k uniformly and independently selected bins to choose from for the location of each ball, one can achieve a maximal load of log_k log n, simply by putting each ball in the least loaded of the k bins. To implement this simple algorithm, one needs to keep track of the status of the entire array of n bins, which requires about n bits of memory. In this work, we find a tradeoff between the number of choices, k, and the number of memory bits available, m. This tradeoff has a sharp threshold governing the performance: If kmn then one can achieve a constant maximal load. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1214/09-AAP656 | Annals of Applied Probability |
Keywords | Field | DocType |
n ball,maximal load,k bin,n bit,log_k log n,log log n ball,choice-memory tradeoff,loaded bin,constant maximal load,n bin,log n,algorithm design and analysis,lower bound,memory management,computational complexity,resource management,upper and lower bounds,random variables,history | Log-log plot,Binary logarithm,Discrete mathematics,Random variable,Combinatorics,Algorithm design,Bin,Ball (bearing),Memory management,Mathematics,Computational complexity theory | Conference |
Volume | Issue | ISSN |
20 | 4 | Annals of Applied Probability 2010, Vol. 20, No. 4, 1470-1511 |
Citations | PageRank | References |
1 | 0.39 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| Eyal Lubetzky | 2 | 355 | 28.87 |
| Ori Gurel-Gurevich | 3 | 29 | 4.03 |