Balanced allocation of online balls-and-bins has long been an active area of
research for efficient load balancing and hashing applications. There exists a
large number of results in this domain with different settings, such as
parallel allocations [1], multi-dimensional allocations [5], weighted balls [4]
etc. For sequential multi-choice allocation where m balls are thrown into n
bins with each ball choosing d (constant) bins independently uniformly at
random, the maximum load of a bin is O(log log n)+m/n with high probability
[3]. This offers the current best known allocation scheme. However, for d =
Theta(log n), the gap obtained is of O(1) [9]. A similar constant gap bound has
been established for parallel allocations with O(log* n) communication rounds
[12]. In this paper we propose a novel multi-choice allocation algorithm,
Improved D-choice with Estimated Average (IDEA) achieving a constant gap with
high probability for the sequential single-dimensional online allocation
problem with constant d. We achieve a maximum load of \lceilm/n\rceil with high
probability for constant d choice scheme with approximately constant number of
retries or rounds per ball. We also show that the bound holds even for an
arbitrary large number of balls, m >> n. Further, we generalize this result to
the weighted case, where the balls have weights drawn from an arbitrary weight
distribution with finite variance. We show that the gap in this case is also
independent of the number of balls thrown and is a constant. We also propose
that IDEA provides constant gap bound w.h.p. in the multi-dimensional scenario
for m = n.