Randomized Allocation Processes* (EXTENDED ABSTRACT)
Artur Czumaj, Volker Stemand · 1997
) Artur Czumaj y Volker Stemann z Abstract We investigate various randomized processes allocating balls into bins that arise in applications in dynamic resource allocation and on-line load balancing. We consider the scenario when m balls arriving sequentially are to be allocated into n bins on-line and without using a global controller. Traditionally, the main aim of allocation processes is to place the balls into bins to minimize the maximum load in bins. However, in many applications it is equally important to minimize the number of trails performed by the balls (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 investigate allocation processes that may reallocate the balls. We provide a tight analysis of the maximum load of processes that during placing a new ball may reassign the balls in up to d randomly chosen bins. We study infinite processe...