The Power of Filling in Balanced Allocations

DOI10.1137/23M1552231arXiv2204.04057WikidataQ129195590 ScholiaQ129195590MaRDI QIDQ6188516FDOQ6188516

Authors: Thomas Sauerwald, John Sylvester 

Publication date: 7 February 2024

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

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).

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)

Cites Work

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

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)