Mixing times and ℓ<i>_p</i> bounds for Oblivious routing

Abstract

We study the task of uniformly minimizing all the ℓp norms of the vector of edge loads in an undirected graph while obliviously routing a multicommodity flow. Let G be an undirected graph having m edges and n vertices. Let the performance index π of an oblivious routing algorithm A (on G) be the supremum of its competitive ratios over all ℓp norms, where the adversarial adaptive routing scheme may vary both with norm and the set of demands. We give a expression in closed form for π(Harmonic) for a certain oblivious algorithm Harmonic that uses the “electrical flow”. We show that π(Harmonic) = O(Tmix) where Tmix(G) is the mixing time of the canonical random walk on G and by . These results lead to O(log n) upper bounds on π(Harmonic) for expanders. We independently show that on N × M discrete tori where N ≤ M, π(Harmonic) = O(N).Lastly we can handle a larger class of norms than ℓp, namely those norms that are invariant with respect to all permutations of the canonical basis vectors and reflections about any of them. Two novel aspects of our proofs are the use of interpolation theorems that relate different operator norms, and connections between discrete harmonic functions and random walks.

Locations

• CiteSeer X (The Pennsylvania State University) - View - PDF