The Power of Filling in Balanced Allocations

DOI10.1137/23M1552231MaRDI QIDQ6188516zbMATH OpenWikidataFDO

Authors Thomas Sauerwald, John Sylvester

Publication date 7 February 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.04057

zbMATH Keywords

memorypotential functionsmaximum loadballs-into-binstwo-choicesweighted ballsbalanced allocationsheavily loadedgap bounds

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Analysis of algorithms (68W40) Combinatorial probability (60C05)

Abstract: We introduce a new class of ballanced allocation processes which are primarily characterized by ``filling underloaded bins. A prototypical example is the Packing process: At each round we only take one bin sample, if the load is below the average load, then we place as many balls until the average load is reached; otherwise, we place only one ball. We prove that for any process in this class the gap between the maximum and average load is $mathcalO(logn)$ w.h.p. for any number of balls $mgeq1$. For the Packing process, we also provide a matching lower bound. Additionally, we prove that the Packing process is sample-efficient in the sense that the expected number of balls allocated per sample is strictly greater than one. Finally, we also demonstrate that the upper bound of $mathcalO(logn)$ on the gap can be extended to the Memory process studied by Mitzenmacher, Prabhakar and Shah (2002).

Cites work

• scientific article; zbMATH DE number 5764855 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• scientific article; zbMATH DE number 233956 (Why is no real title available?)
• Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory
• Balanced Allocations
• Balanced Allocations: The Heavily Loaded Case
• Balanced allocation on graphs
• Balanced allocation on hypergraphs
• Balanced allocation: patience is not a virtue
• Balancing games
• Balls and Bins: Smaller Hash Families and Faster Evaluation
• Efficient PRAM simulation on a distributed memory machine
• Graphical balanced allocations and the \((1+\beta )\)-choice process
• Hashing, load balancing and multiple choice
• Inequalities: theory of majorization and its applications
• On the analysis of randomized load balancing schemes
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Quasirandom load balancing
• Randomized allocation processes
• The power of thinning in balanced allocation

This page was built for publication: The Power of Filling in Balanced Allocations

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