Optimal oblivious routing in polynomial time

Yossi Azar; Edith Cohen; Amos Fiat; Haim Kaplan; Harald Räcke

doi:10.1016/j.jcss.2004.04.010

Optimal oblivious routing in polynomial time

Yossi Azar
, Edith Cohen
, Amos Fiat
, Haim Kaplan
, Harald Räcke

Tel Aviv University
AT and T Research Labs
Universität Paderborn

Research output: Contribution to journal › Article › peer-review

51 Scopus citations

Abstract

A recent seminal result of Räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately, Räcke's construction is not polynomial time. We give a polynomial time construction that guarantees Räcke's bounds, and more generally gives the true optimal ratio for any (undirected or directed) network.

Original language	English
Pages (from-to)	383-394
Number of pages	12
Journal	Journal of Computer and System Sciences
Volume	69
Issue number	3 SPEC. ISS.
DOIs	https://doi.org/10.1016/j.jcss.2004.04.010
State	Published - Nov 2004
Externally published	Yes

Keywords

Communication networks
Oblivious ratio
Oblivious routing

Access to Document

10.1016/j.jcss.2004.04.010

Cite this

@article{e90f90fdc51f4c508af98c05c3e9b632,

title = "Optimal oblivious routing in polynomial time",

abstract = "A recent seminal result of R{\"a}cke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately, R{\"a}cke's construction is not polynomial time. We give a polynomial time construction that guarantees R{\"a}cke's bounds, and more generally gives the true optimal ratio for any (undirected or directed) network.",

keywords = "Communication networks, Oblivious ratio, Oblivious routing",

author = "Yossi Azar and Edith Cohen and Amos Fiat and Haim Kaplan and Harald R{\"a}cke",

year = "2004",

month = nov,

doi = "10.1016/j.jcss.2004.04.010",

language = "English",

volume = "69",

pages = "383--394",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "3 SPEC. ISS.",

}

TY - JOUR

T1 - Optimal oblivious routing in polynomial time

AU - Azar, Yossi

AU - Cohen, Edith

AU - Fiat, Amos

AU - Kaplan, Haim

AU - Räcke, Harald

PY - 2004/11

Y1 - 2004/11

N2 - A recent seminal result of Räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately, Räcke's construction is not polynomial time. We give a polynomial time construction that guarantees Räcke's bounds, and more generally gives the true optimal ratio for any (undirected or directed) network.

AB - A recent seminal result of Räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately, Räcke's construction is not polynomial time. We give a polynomial time construction that guarantees Räcke's bounds, and more generally gives the true optimal ratio for any (undirected or directed) network.

KW - Communication networks

KW - Oblivious ratio

KW - Oblivious routing

UR - https://www.scopus.com/pages/publications/4544383696

U2 - 10.1016/j.jcss.2004.04.010

DO - 10.1016/j.jcss.2004.04.010

M3 - Article

AN - SCOPUS:4544383696

SN - 0022-0000

VL - 69

SP - 383

EP - 394

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3 SPEC. ISS.

ER -

Optimal oblivious routing in polynomial time

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this