The Library
Multiple-choice balanced allocation in (almost) parallel
Tools
Berenbrink, Petra, Czumaj, Artur, Englert, Matthias, Friedetzky, Thomas and Nagel, Lars (2012) Multiple-choice balanced allocation in (almost) parallel. In: Gupta , Anupam and Jansen , Klaus and Rolim , José and Servedio , Rocco , (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques : 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings. Lecture Notes in Computer Science, Volume 7408 . Berlin Heidelberg: Springer-Verlag, pp. 411-422. ISBN 9783642325113
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-32512-0_35
Abstract
We consider the problem of resource allocation in a parallel environment where new incoming resources are arriving online in groups or batches.
We study this scenario in an abstract framework of allocating balls into bins. We revisit the allocation algorithm \sc Greedy[2] due to Azar, Broder, Karlin, and Upfal (SIAM J. Comput. 1999), in which, for sequentially arriving balls, each ball chooses two bins at random, and gets placed into one of those two bins with minimum load. The maximum load of any bin after the last ball is allocated by \sc Greedy[2] is well understood, as is, indeed, the entire load distribution, for a wide range of settings. The main goal of our paper is to study balls and bins allocation processes in a parallel environment with the balls arriving in batches. In our model, m balls arrive in batches of size n each (with n being also equal to the number of bins), and the balls in each batch are to be distributed among the bins simultaneously. In this setting, we consider an algorithm that uses \sc Greedy[2] for all balls within a given batch, the answers to those balls’ load queries are with respect to the bin loads at the end of the previous batch, and do not in any way depend on decisions made by other balls from the same batch.
Our main contribution is a tight analysis of the new process allocating balls in batches: we show that after the allocation of any number of batches, the gap between maximum and minimum load is O(logn) with high probability, and is therefore independent of the number of batches used.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer-Verlag | ||||
Place of Publication: | Berlin Heidelberg | ||||
ISBN: | 9783642325113 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques : 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings | ||||
Editor: | Gupta , Anupam and Jansen , Klaus and Rolim , José and Servedio , Rocco | ||||
Official Date: | 2012 | ||||
Dates: |
|
||||
Volume: | Volume 7408 | ||||
Page Range: | pp. 411-422 | ||||
DOI: | 10.1007/978-3-642-32512-0_35 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |