| Abstract: | Many dynamic resource allocation and on‐line load balancing problems can be modeled by processes that sequentially allocate balls into bins. The balls arrive one by one and are to be placed into bins on‐line without using a centralized controller. If n balls are sequentially placed into n bins by placing each ball in a randomly chosen bin, then it is widely known that the maximum load in bins is ln n /ln ln n?(1+o(1)) with high probability. Azar, Broder, Karlin, and Upfal extended this scheme, so that each ball is placed sequentially into the least full of d randomly chosen bins. They showed that the maximum load of the bins reduces exponentially and is ln ln n/In d+Θ(1) with high probability, provided d<2. In this paper we investigate various extensions of these schemes that arise in applications in dynamic resource allocation and on‐line load balancing. Traditionally, the main aim of allocation processes is to place balls into bins to minimize the maximum load in bins. However, in many applications it is equally important to minimize the number of choices performed (the allocation time). We study adaptive allocation schemes that achieve optimal tradeoffs between the maximum load, the maximum allocation time, and the average allocation time. We also investigate allocation processes that may reallocate the balls. We provide a tight analysis of a natural class of processes that each time a ball is placed in one of d randomly chosen bins may move balls among these d bins arbitrarily. Finally, we provide a tight analysis of the maximum load of the off‐line process in which each ball may be placed into one of d randomly chosen bins. We apply this result to competitive analysis of on‐line load balancing processes. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 297–331, 2001 |
