An Improved Drift Theorem for Balanced Allocations
Abstract
References
Index Terms
- An Improved Drift Theorem for Balanced Allocations
Recommendations
Balanced Allocations in Batches: The Tower of Two Choices
SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and ArchitecturesIn the balanced allocation framework, the goal is to allocate m balls into n bins, so as to minimize the gap (difference of maximum to average load). The One-Choice process allocates each ball to a bin sampled independently and uniformly at random. The ...
Balanced Allocations with the Choice of Noise
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed ComputingWe consider the allocation of m balls (jobs) into n bins (servers). In the standard Two-Choice process, at each step t = 1, 2, . . . ,m we first sample two randomly chosen bins, compare their two loads and then place a ball in the least loaded bin. It ...
Comments
Information & Contributors
Information
Published In
![cover image ACM Transactions on Algorithms](/cms/asset/a480ab6b-5f05-46e2-ae42-38ab5c8e46de/3613685.cover.jpg)
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 132Total Downloads
- Downloads (Last 12 months)132
- Downloads (Last 6 weeks)11
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in