An improved drift theorem for balanced allocations

DOI10.1145/3673900MaRDI QIDQ7023538zbMATH OpenFDO

Authors Thomas Sauerwald

Publication date 21 February 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3673900

zbMATH Keywords

balanced allocationsballs-into-binsdrift theoremmaximum loadpotential functionstwo-choicesweighted balls

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites work

• Balanced allocation on dynamic hypergraphs
• Balanced allocation on graphs
• Balanced Allocations
• Balanced Allocations with Heterogeneous Bins: The Power of Memory
• Balanced allocations: caching and packing, twinning and thinning
• Balanced Allocations: The Heavily Loaded Case
• Balanced allocations: the heavily loaded case with deletions
• Concentration of Measure for the Analysis of Randomized Algorithms
• Efficient PRAM simulation on a distributed memory machine
• Graphical balanced allocations and the (1+ )-choice process
• Hashing, load balancing and multiple choice
• scientific article; zbMATH DE number 5485459 (Why is no real title available?)
• scientific article; zbMATH DE number 5764855 (Why is no real title available?)
• scientific article; zbMATH DE number 6850453 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• scientific article; zbMATH DE number 7829335 (Why is no real title available?)
• scientific article; zbMATH DE number 7832755 (Why is no real title available?)
• Load balancing under \(d\)-thinning
• Long-term balanced allocation via thinning
• Multiple-choice balanced allocation in (almost) parallel
• On the analysis of randomized load balancing schemes
• Parallel randomized load balancing
• Parallel randomized load balancing: a lower bound for a more general model
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Randomized allocation processes
• Self-stabilizing balls and bins in batches. The power of leaky bins
• The power of choice in priority scheduling
• The power of thinning in balanced allocation
• The power of two choices in graphical allocation
• Tight bounds for parallel randomized load balancing, extended abstract

This page was built for publication: An improved drift theorem for balanced allocations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7023538)