Oblivious Routing in the $L_p$ norm

Oblivious Routing in the $L_p$ norm

Tue, 10/11/2009
14:00 		Harald Raecke (Warwick) Combinatorial Theory Seminar Add to calendar L3
Oblivious Routing in the $ L_p $ norm
HTML clipboard Gupta et al. introduced a very general multi-commodity flow problem in which the cost of a given flow solution on a graph $ G=(V,E) $ is calculated by first computing the link loads via a load-function l, that describes the load of a link as a function of the flow traversing the link, and then aggregating the individual link loads into a single number via an aggregation function.   We show the existence of an oblivious routing scheme with competitive ratio $ O(\log n) $ and a lower bound of $ \Omega(\log n/\logl\og n) $ for this model when the aggregation function agg is an $ L_p $-norm.   Our results can also be viewed as a generalization of the work on approximating metrics by a distribution over dominating tree metrics and the work on minimum congestion oblivious. We provide a convex combination of trees such that routing according to the tree distribution approximately minimizes the $ L_p $-norm of the link loads. The embedding techniques of Bartal and Fakcharoenphol et al. [FRT03] can be viewed as solving this problem in the $ L_1 $-norm while the result on congestion minmizing oblivious routing solves it for $ L_\infty $. We give a single proof that shows the existence of a good tree-based oblivious routing for any $ L_p $-norm.