Optimal oblivious routing in polynomial time

被引：47

作者：

Azar, Y

Cohen, E

Fiat, A

Kaplan, H

Räcke, H

机构：

[1] AT&T Labs Res, Florham Pk, NJ 07932 USA

[2] Tel Aviv Univ, Sch Comp Sci, IL-69978 Tel Aviv, Israel

[3] Paderborn Univ, Dept Math & Comp Sci, D-33102 Paderborn, Germany

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2004年 / 69卷 / 03期

关键词：

oblivious routing; oblivious ratio; communication networks;

D O I：

10.1016/j.jcss.2004.04.010

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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

引用

页码：383 / 394

页数：12

共 15 条

[1]

APPLEGATE D, 2003, P ACM SIGCOMM 03 C

[2] On-line routing of virtual circuits with applications to load balancing and machine scheduling [J].

Aspnes, J ;

Azar, Y ;

Fiat, A ;

Plotkin, S ;

Waarts, O .

JOURNAL OF THE ACM, 1997, 44 (03) :486-504

[3]

AWERBUCH B, 1994, FOCS, V35, P240

[4]

Bansal N., 2003, P 15 ANN ACM S PAR A, P44, DOI DOI 10.1145/777412.777420

[5]

Bienkowski M., 2003, P 15 ANN ACM S PAR A, P24

[6] ROUTING, MERGING, AND SORTING ON PARALLEL MODELS OF COMPUTATION [J].

BORODIN, A ;

HOPCROFT, JE .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (01) :130-145

[7]

Harrelson Chris, 2003, SPAA 2003, P34, DOI [10.1145/777412, DOI 10.1145/777412]

[8]

KAKALAMANIS C, 1990, P 2 ANN ACM S PAR AL, P31

[9]

Leighton F.T., 1992, Introduction to Parallel Algorithms and Architecture: Arrays. Trees. Hypercubes

[10]

Leonardi S, 1998, LECT NOTES COMPUT SC, V1442, P242, DOI 10.1007/BFb0029572

← 1 2 →