The power of thinning in balanced allocation

DOI10.1214/21-ECP400zbMath1494.60012arXiv1807.01132MaRDI QIDQ2064870

Ori Gurel-Gurevich, Ohad Noy Feldheim

Publication date: 6 January 2022

Published in: Electronic Communications in Probability (Search for Journal in Brave)

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

zbMATH Keywords

thinningload balancingsubsamplingballs and binsone-retrytwo-choices

Mathematics Subject Classification ID

Combinatorial probability (60C05) Online algorithms; streaming algorithms (68W27)

Related Items (4)

The power of online thinning in reducing discrepancy ⋮ Long-term balanced allocation via thinning ⋮ Balanced allocation on hypergraphs ⋮ The Power of Filling in Balanced Allocations

Cites Work

• Unnamed Item
• How asymmetry helps load balancing
• Graphical balanced allocations and the (1 + β)-choice process
• Uniform Central Limit Theorems
• Balanced Allocations
• Balanced Allocation: Patience is not a Virtue
• Parallel randomized load balancing
• Balanced Allocations: A Simple Proof for the Heavily Loaded Case
• Probability and Computing
• Balanced Allocations: The Heavily Loaded Case

This page was built for publication: The power of thinning in balanced allocation