Balanced Allocations: A Simple Proof for the Heavily Loaded Case

DOI10.1007/978-3-662-43948-7_81zbMath1410.68073arXiv1310.5367OpenAlexW2963296267MaRDI QIDQ5167808

Kunal Talwar, Udi Wieder

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (9)

Balanced Allocation: Patience Is Not a Virtue ⋮ The power of online thinning in reducing discrepancy ⋮ Dynamic local searchable symmetric encryption ⋮ Long-term balanced allocation via thinning ⋮ A simple approach for adapting continuous load balancing processes to discrete settings ⋮ A generalization of multiple choice balls-into-bins: tight bounds ⋮ Self-stabilizing balls and bins in batches. The power of leaky bins ⋮ The power of thinning in balanced allocation ⋮ Dynamic averaging load balancing on cycles

This page was built for publication: Balanced Allocations: A Simple Proof for the Heavily Loaded Case