Multiple-choice balanced allocation in (almost) parallel

DOI10.1007/978-3-642-32512-0_35MaRDI QIDQ3167413zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Petra Berenbrink, Matthias Englert, Tom Friedetzky, Lars Nagel, Artur Czumaj

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32512-0_35

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Recommendations

• Randomized allocation processes
• Revisiting Randomized Parallel Load Balancing Algorithms
• Balanced Allocations
• Balanced allocations (extended abstract)
• Balanced Allocations: The Heavily Loaded Case

Cited in

(9)

• Almost budget-balanced VCG mechanisms to assign multiple objects
• Balanced allocations and global clock in population protocols: an accurate analysis
• Self-stabilizing balls and bins in batches. The power of leaky bins
• Singletons for simpletons revisiting windowed backoff with Chernoff bounds
• Contention resolution with constant throughput and log-logstar channel accesses
• A generalization of multiple choice balls-into-bins: tight bounds
• Self-stabilizing balls \& bins in batches: the power of leaky bins (extended abstract)
• An improved drift theorem for balanced allocations
• Balanced allocations with the choice of noise

This page was built for publication: Multiple-choice balanced allocation in (almost) parallel

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