Title :
Oblivious Routing for the Lp-norm
Author :
Englert, Matthias ; Racke, H.
Author_Institution :
Dept. of Comput. Sci., Univ. of Warwick, Coventry, UK
Abstract :
Gupta et al. [13] introduced a very general multicommodity 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 ¿, 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 agg:R|E| ¿ R. In this paper we show the existence of an oblivious routing scheme with competitive ratio O(log n) and a lower bound of ¿(log n/log log n) 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 (see e.g. [4], [5], [8]) and the work on minimum congestion oblivious routing [20], [14], [21]. 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 [4], [5] and Fakcharoenphol et al. [8] can be viewed as solving this problem in the L1-norm while the result of Racke [21] solves it for L¿. We give a single proof that shows the existence of a good tree-based oblivious routing for any Lp-norm. For the Euclidean norm, we also show that it is possible to compute a tree-based oblivious routing scheme in polynomial time.
Keywords :
computational complexity; trees (mathematics); Lp-norm; aggregation function; competitive ratio; computational complexity; embedding techniques; link loads; load-function; multicommodity flow problem; polynomial time; tree distribution; tree metrics; tree-based oblivious routing; Algorithm design and analysis; Computer science; Cost function; Polynomials; Quality of service; Routing; Telecommunication traffic; metric embeddings; norm; oblivious routing;
Conference_Titel :
Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on
Conference_Location :
Atlanta, GA
Print_ISBN :
978-1-4244-5116-6
DOI :
10.1109/FOCS.2009.52