The Power of Filling in Balanced Allocations

DOI10.1137/23m1552231arXiv2204.04057WikidataQ129195590 ScholiaQ129195590MaRDI QIDQ6188516

John Sylvester, Unnamed Author, Thomas Sauerwald

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

potential functionsmemorymaximum loadballs-into-binstwo-choicesweighted ballsbalanced allocationsheavily loadedgap bounds

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Balancing games
• On the analysis of randomized load balancing schemes
• Efficient PRAM simulation on a distributed memory machine
• Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory
• The power of thinning in balanced allocation
• Randomized allocation processes
• Quasirandom Load Balancing
• Graphical balanced allocations and the (1 + β)-choice process
• Balanced allocation on graphs
• Balanced Allocations
• Balanced Allocation: Patience is not a Virtue
• Hashing, Load Balancing and Multiple Choice
• Balanced Allocations: The Heavily Loaded Case
• Balls and Bins: Smaller Hash Families and Faster Evaluation
• Inequalities: theory of majorization and its applications
• Balanced allocation on hypergraphs

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