Balanced allocation on graphs: a random walk approach

DOI10.1007/978-3-319-42634-1_27zbMATH Open1479.05330arXiv1407.2575OpenAlexW1576721941MaRDI QIDQ2817876FDOQ2817876

Ali Pourmiri

Publication date: 2 September 2016

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

Abstract: In this paper we propose algorithms for allocating $n$ sequential balls into $n$ bins that are interconnected as a $d$-regular $n$-vertex graph $G$, where $dge3$ can be any integer.Let $l$ be a given positive integer. In each round $t$, $1letlen$, ball $t$ picks a node of $G$ uniformly at random and performs a non-backtracking random walk of length $l$ from the chosen node.Then it allocates itself on one of the visited nodes with minimum load (ties are broken uniformly at random). Suppose that $G$ has a sufficiently large girth and $d=omega(logn)$. Then we establish an upper bound for the maximum number of balls at any bin after allocating $n$ balls by the algorithm, called {it maximum load}, in terms of $l$ with high probability. We also show that the upper bound is at most an $O(loglogn)$ factor above the lower bound that is proved for the algorithm. In particular, we show that if we set $l=lfloor(logn{)}^{frac1+epsilon2}floor$, for every constant $epsilonin(0,1)$, and $G$ has girth at least $omega(l)$, then the maximum load attained by the algorithm is bounded by $O(1/epsilon)$ with high probability.Finally, we slightly modify the algorithm to have similar results for balanced allocation on $d$-regular graph with $din[3,O(logn)]$ and sufficiently large girth.

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

Recommendations

• Balanced allocation on graphs: a random walk approach
• Graphical balanced allocations and the \((1+\beta )\)-choice process
• Balls into bins via local search
• Perfectly balanced allocation
• Randomized allocation processes

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)

Cites Work

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

Cited In (3)

• Balanced allocation on hypergraphs
• Balanced allocation on dynamic hypergraphs
• Derandomized Balanced Allocation

This page was built for publication: Balanced allocation on graphs: a random walk approach

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