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