Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Balanced Allocation on Graphs: A Random Walk Approach


Pourmiri,  Ali
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 619KB

Supplementary Material (public)
There is no public supplementary material available

Pourmiri, A. (2014). Balanced Allocation on Graphs: A Random Walk Approach. Retrieved from http://arxiv.org/abs/1407.2575.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-45B1-2
In this paper we propose an algorithm for allocating $n$ sequential balls into $n$ bins that are organized as a $n$-vertex $d$-regular graph $G$, where $d\ge3$ can be any integer. Let $L$ be a given positive integer. In each round $t$, $1\leq t\leq n$, ball $t$ picks a node of $G$ uniformly at random and performs a non-backtracking random walk (NBRW) of length $L$ from the chosen node. Then it deterministically selects a subset of the visited nods as the potential choices and allocates itself on one of the choices with minimum load (ties are broken uniformly at random). Suppose that $G$ has girth at least $\Omega(L(\log L+\log\log d))$. 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(\log L+\log\log d)$ factor above the lower bound that is proved for the algorithm. In particular we show that if $G$ has girth at least $(\log n)^{\frac{1+\epsilon}{2}} $, for any constant $\epsilon\in(0,1]$ and we set $L=\lfloor (\log n)^{\frac{1+\delta}{2}} \rfloor$, where $0<\delta<\epsilon$ is a constant, then the maximum load is bounded by $O(1/\delta)$ with high probability. Finally, we present some more general results which hold for a variant of this algorithm.