TY - GEN
T1 - Oblivious routing for the Lp-norm
AU - Englert, Matthias
AU - Räcke, Harald
PY - 2009
Y1 - 2009
N2 - Gupta et al. [13] 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 ℓ, 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: ℝ|E| → ℝ. 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 Li-norm while the result of Räcke [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.
AB - Gupta et al. [13] 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 ℓ, 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: ℝ|E| → ℝ. 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 Li-norm while the result of Räcke [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.
KW - Metric embeddings
KW - Norm
KW - Oblivious routing
UR - http://www.scopus.com/inward/record.url?scp=77952349409&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2009.52
DO - 10.1109/FOCS.2009.52
M3 - Conference contribution
AN - SCOPUS:77952349409
SN - 9780769538501
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 32
EP - 40
BT - Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009
T2 - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009
Y2 - 25 October 2009 through 27 October 2009
ER -