Balanced allocation on dynamic hypergraphs

DOI10.4230/LIPICS.APPROX/RANDOM.2020.11MaRDI QIDQ6084354zbMATH OpenOpenAlexFDO

Authors Catherine Greenhill, Bernard Mans, Ali Pourmiri

Publication date 31 October 2023

Full work available at URL https://arxiv.org/pdf/2006.07588

zbMATH Keywords

balanced allocationballs-into-binspower of two choiceswitness tree technique

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 5764855 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• Balanced Allocations
• Balanced allocation on graphs
• Balls and bins: smaller hash families and faster evaluation
• Balls into bins via local search
• Balls into bins with related random choices
• Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
• Derandomized Balanced Allocation
• Graphical balanced allocations and the (1+ )-choice process
• Hashing, load balancing and multiple choice
• How asymmetry helps load balancing
• Power of \(d\) choices with simple tabulation
• Regular graphs of large girth and arbitrary degree
• The power of two choices with simple tabulation

Cited in

(4)

• Axiomatization and Core Stability of Allocation Rules for Hypergraph Situations
• An improved drift theorem for balanced allocations
• Balanced allocations with the choice of noise
• Derandomized Balanced Allocation

This page was built for publication: Balanced allocation on dynamic hypergraphs

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