The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
Balanced Allocations
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal,
Pages. 180-200
Abstract Suppose that we sequentially place $n$ balls into $n$ boxes by
putting each ball into a randomly chosen box. It is well known
that when we are done, the fullest box has with high probability $(1+o(1))ln n/lnln n$
balls in it. Suppose instead that for each ball we choose two
boxes at random and place the ball into the one which is less full
at the time of placement. We show that with high probability, the
fullest box contains only in $ln ln n/ln 2+O(1)$
balls-exponentially less than before. Furthermore, we show that a
similar gap exists in the infinite process, where at each step one
ball, chosen uniformly at random, is deleted, and one ball is
added in the manner above. We discuss consequences of this and
related theorems for dynamic resource allocation, hashing, and
on-line load balancing.
Contents 1. Introduction 1.1. Applications 1.1.1. Dynamic resource allocation 1.1.2. Hashing 1.1.3. Competitive on-line load balancing 2. Definitions and notation 3. The finite process 4. The infinite process 5. Hashing 6. Competitive on-line load balancing 6.1.
Preliminaries 6.1.1. Permanent tasks 6.1.2. Temporary tasks 7.
Experimental results
Key words urn models, occupancy problems, on-line algorithms, resource allocation, hashing, load balancing
Mathmatical Subject Classification 68Q25, 68M20, 68P10, 60G99, 60