Oblivious routing for the Lp-norm
Englert, Matthias and Räcke, Harald (2009) Oblivious routing for the Lp-norm. In: 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, October 25-27 2009. Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science pp. 32-40.
05438649.pdf - Published Version
Restricted to Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Official URL: http://dx.doi.org/10.1109/FOCS.2009.52
Gupta et al.  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 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 agg : R-vertical bar E vertical bar -> R.
In this paper we show the existence of an oblivious routing scheme with competitive ratio O (log n) and a lower bound of Omega(log n/log log 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 (see e. g. , , ) and the work on minimum congestion oblivious routing , , . 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.  can be viewed as solving this problem in the L-1-norm while the result of Racke  solves it for L-1. We give a single proof that shows the existence of a good tree-based oblivious routing for any L-p-norm.
For the Euclidean norm, we also show that it is possible to compute a tree-based oblivious routing scheme in polynomial time.
|Item Type:||Conference Item (Paper)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Divisions:||Faculty of Science > Computer Science|
|Series Name:||ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE|
|Journal or Publication Title:||2009 50th Annual IEEE Symposium on Foundations of Computer Science|
|Publisher:||IEEE Computer Society|
|Number of Pages:||9|
|Page Range:||pp. 32-40|
|Access rights to Published version:||Restricted or Subscription Access|
|Funder:||Engineering and Physical Sciences Research Council (EPSRC), The Centre for Discrete Mathematics and its Applications (DIMAP)|
|Conference Paper Type:||Paper|
|Title of Event:||50th Annual IEEE Symposium on Foundations of Computer Science|
|Type of Event:||Conference|
|Location of Event:||Atlanta, GA|
|Date(s) of Event:||October 25-27 2009|
Actions (login required)