Balanced Allocation: Patience Is Not a Virtue

DOI10.1137/17M1155375MaRDI QIDQ5885582zbMATH OpenOpenAlexFDO

Authors Amanda Redlich, Eli Upfal, John Augustine, William K. jun. Moses

Publication date 4 April 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/17m1155375

zbMATH Keywords

\(\mathsf{FirstDiff}\)balanced allocationload balancingrandomized algorithmstask allocation

Mathematics Subject Classification ID

Combinatorial probability (60C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorics in computer science (68R05)

Recommendations

• Balanced allocation: patience is not a virtue
• Balanced allocations (extended abstract)
• Balanced Allocations
• Randomized allocation processes
• Revisiting randomized parallel load balancing algorithms

Cites work

• Balanced allocation: patience is not a virtue
• Balanced Allocations
• Balanced allocations: a simple proof for the heavily loaded case
• Balanced Allocations: The Heavily Loaded Case
• How asymmetry helps load balancing
• scientific article; zbMATH DE number 3727274 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• Probability and Computing
• Randomized allocation processes
• Tail bounds for sums of geometric and exponential variables
• The \((1 + {\beta})\)-choice process and weighted balls-into-bins

Cited in

(7)

• The power of thinning in balanced allocation
• A study on load-balanced variants of the bin packing problem
• Multidimensional balanced allocations
• Balanced allocations: the heavily loaded case
• Randomized load balancing by joining and splitting bins
• Balanced allocation: patience is not a virtue
• Studying Balanced Allocations with Differential Equations

This page was built for publication: Balanced Allocation: Patience Is Not a Virtue

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