The Library
Oblivious routing for the Lp-norm
Tools
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. ISBN 9780769538501. doi:10.1109/FOCS.2009.52 ISSN 0272-5428.
PDF
05438649.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (281Kb) |
Official URL: http://dx.doi.org/10.1109/FOCS.2009.52
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 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. [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 L-p-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 L-1-norm while the result of Racke [21] 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, Engineering and Medicine > 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 | ||||
ISBN: | 9780769538501 | ||||
ISSN: | 0272-5428 | ||||
Official Date: | 2009 | ||||
Dates: |
|
||||
Number of Pages: | 9 | ||||
Page Range: | pp. 32-40 | ||||
DOI: | 10.1109/FOCS.2009.52 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 3 December 2015 | ||||
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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |