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
    Aspnes, J
    Azar, Y
    Fiat, A
    Plotkin, S
    Waarts, O
    [J]. 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
    BORODIN, A
    HOPCROFT, JE
    [J]. 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
12