Englert, Matthias and Räcke, Harald (2009) Oblivious routing for the L-p-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.

Full text not available from this repository.

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 > 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:	978-0-7695-3850-1
ISSN:	0272-5428
Date:	2009
Number of Pages:	9
Page Range:	pp. 32-40
Identification Number:	10.1109/FOCS.2009.52
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
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
URI:	http://wrap.warwick.ac.uk/id/eprint/5800

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item