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

Publikation: Beitrag in Fachzeitschrift › Artikel › Begutachtung

50 Zitate (Scopus)

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.

Originalsprache	Englisch
Seiten (von - bis)	383-394
Seitenumfang	12
Fachzeitschrift	Journal of Computer and System Sciences
Jahrgang	69
Ausgabenummer	3 SPEC. ISS.
DOIs	https://doi.org/10.1016/j.jcss.2004.04.010
Publikationsstatus	Veröffentlicht - Nov. 2004
Extern publiziert	Ja

Zugriff auf Dokument

10.1016/j.jcss.2004.04.010

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

@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

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Dieses zitieren