Date
Tue, 10 Nov 2009
Time
14:00 - 14:50
Location
L3
Speaker
Harald Raecke
Organisation
Warwick
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(logn) and a lower bound of Ω(logn/\logl\ogn) for this model when the aggregation function agg is an Lp-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 Lp-norm of the link loads. The embedding techniques of Bartal and Fakcharoenphol et al. [FRT03] can be viewed as solving this problem in the L1-norm while the result on congestion minmizing oblivious routing solves it for L. We give a single proof that shows the existence of a good tree-based oblivious routing for any Lp-norm.

Last updated on 6 May 2025, 2:04pm. Please contact us with feedback and comments about this page.