TIME: 1:30-2:20 pm,  May 16, 2006

PLACE: CSE 403

TITLE: Balanced Allocation on Graphs

SPEAKER:  Krishnaram Kenthapadi
          Stanford University

ABSTRACT:

It is well known that if $n$ balls are inserted into $n$ bins, with high 
probability, the bin with maximum load contains $(1+ o(1)) \log n / 
\log\log n$ balls. Azar, Broder, Karlin, and Upfal showed that instead of 
choosing one bin, if $d \ge 2$ bins are chosen at random and the ball 
inserted into the least loaded of the $d$ bins, the maximum load reduces 
drastically to $\log\log n /\log d + O(1)$.

We study the two choice balls and bins process when balls are not allowed 
to choose any two random bins, but only bins that are connected by an edge 
in an underlying graph. We show that for $n$ balls and $n$ bins, if the 
graph is almost regular with degree $n^\epsilon$, where $\epsilon$ is not 
too small, the previous bounds on the maximum load continue to hold. 
Precisely, the maximum load is $\log \log n + O(1/\epsilon) + O(1)$. So 
even if the graph has degree $n^{\Omega(1/\log\log n)}$, the maximum load 
is $O(\log\log n)$. For general $\Delta$-regular graphs, we show that the 
maximum load is $\log\log n + O(\frac{\log n}{\log (\Delta/\log^4 n)}) + 
O(1)$ and also provide an almost matching lower bound of $\log \log n + 
\frac{\log n}{\log (\Delta \log n)}$. Further this does not hold for 
non-regular graphs even if the minimum degree is high.

Voecking showed that the maximum bin size with $d$ choice load balancing 
can be further improved to $\log\log n /d + O(1)$ by breaking ties to the 
left. This requires $d$ random bin choices. We show that such bounds can 
be achieved by making two random accesses and querying $d/2$ contiguous 
bins in each access. By grouping a sequence of $n$ bins into $2n/d$ 
groups, each of $d/2$ consecutive bins, if each ball chooses two groups at 
random and inserts the new ball into the least-loaded bin in the lesser 
loaded group, then the maximum load is $\log\log n/d + O(1)$ with high 
probability. Furthermore, it also turns out that this grouping into groups 
of size $d/2$ is also essential in achieving this bound, that is, instead 
of choosing two random groups, if we simply choose two random sets of 
$d/2$ consecutive bins, then the maximum load jumps to $\log\log n /\log 
d$.

Joint work with Rina Panigrahy.

Paper available at: 
http://theory.stanford.edu/~kngk/papers/balancedAllocationOnGraphs.pdf