Name
Abstract | ||
|---|---|---|
This paper studies the maximum load in the approximatedd-choice balls-and-bins game where the current load of each bin is available only approximately In the model of this game, we have r thresholds T1,...,Tr(0T1Tr) for an integer r (≥ 1) For each ball, we select d bins and put the ball into the bin of the lowest range, i.e., the bin of load i such that Tk ≤ i ≤ Tk+1–1 and no other selected bin has height less than Tk If there are two or more bins in the lowest range (i.e., their height is between Tk and Tk+1–1), then we assume that those bins cannot be distinguished and so one of them is selected uniformly at random We then estimate the maximum load for n balls and n bins in this game In particular, when we put the r thresholds at a regular interval of an appropriate Δ, i.e., Tr−Tr−1=...T2−T1=T1=Δ, the maximum load L(r) is given as $(r+O(1))\sqrt[r+1]{\frac{r+1}{(d-1)^{r}}{\rm ln}{\it n}/{\rm ln}(\frac{r+1}{(d-1)^{r}}{\rm ln}{\it n})}$ The bound is also described as L(Δ) ≤ {(1 + o(1))ln ln n + O(1)}Δ/ln ((d – 1)Δ) using parameter Δ Thus, if Δ is a constant, this bound matches the (tight) bound in the original d-choice model given by Azar et al., within a constant factor The bound is also tight within a constant factor when r = 1. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-30551-4_48 | ISAAC |
Keywords | Field | DocType |
n ball,lowest range,constant factor,current load,rm ln,randomized load balancing,bound match,n bin,ln ln n,maximum load,load i,load balance | Integer,Discrete mathematics,Combinatorics,Algorithmics,Bin,Load balancing (computing),Ball (bearing),Mathematics | Conference |
Volume | ISSN | ISBN |
3341 | 0302-9743 | 3-540-24131-0 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuo Iwama | 1 | 1400 | 153.38 |
| Akinori Kawachi | 2 | 185 | 20.66 |