Balanced Allocation on Graphs: A Random Walk Approach

DOI10.1007/978-3-319-42634-1_27zbMath1479.05330arXiv1407.2575OpenAlexW1576721941MaRDI QIDQ2817876

Ali Pourmiri

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science, Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

maximum load\(d\)-regular graphbalanced allocationballs-into-bins modelballs-into-bins modelsnonbacktracking random walks

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Random walks on graphs (05C81)

Related Items (2)

Balanced allocation on hypergraphs ⋮ Balanced allocation on dynamic hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Balls into bins with related random choices
• Regular graphs of large girth and arbitrary degree
• Poisson approximation for non-backtracking random walks
• Multiple Random Walks in Random Regular Graphs
• How asymmetry helps load balancing
• Graphical balanced allocations and the (1 + β)-choice process
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Balanced allocation on graphs
• Balanced Allocations
• Balls into Bins via Local Search

This page was built for publication: Balanced Allocation on Graphs: A Random Walk Approach