Approximation algorithms for disjoint paths and related routing and packing problems

被引：49

作者：

Baveja, A ^{[1
]}

Srinivasan, A

机构：

[1] Rutgers State Univ, Sch Business, Camden, NJ 08102 USA

[2] Bell Labs, Lucent Technol, Murray Hill, NJ 07974 USA

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 2000年 / 25卷 / 02期

关键词：

disjoint paths; approximation algorithms; unsplittable flow; routing; packing; integer programming; multicommodity flow; randomized algorithms; rounding; linear programming;

D O I：

10.1287/moor.25.2.255.12228

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improved approximation algorithms and/or integrality gaps for all problems considered; the central theme of this work is the underlying multicommodity flow relaxation. Applications of these techniques to approximating families of packing integer programs are also presented.

引用

页码：255 / 280

页数：26

共 40 条

[1] Efficient routing in optical networks [J].

Aggarwal, A ;

BarNoy, A ;

Coppersmith, D ;

Ramaswami, R ;

Schieber, B ;

Sudan, M .

JOURNAL OF THE ACM, 1996, 43 (06) :973-1001

[2]

Ahuja RK, 1993, NETWORK FLOWS THEORY

[3] On-line algorithms for path selection in a nonblocking network [J].

Arora, S ;

Leighton, FT ;

Maggs, BM .

SIAM JOURNAL ON COMPUTING, 1996, 25 (03) :600-625

[4]

AUMANN Y, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P567

[5]

Awerbuch B., 1994, Proceedings. 35th Annual Symposium on Foundations of Computer Science (Cat. No.94CH35717), P412, DOI 10.1109/SFCS.1994.365675

[6]

AWERBUCH B, P ACM S THEOR COMP A, P489

[7] A USEFUL ELEMENTARY CORRELATION-INEQUALITY [J].

BOPPONA, R ;

SPENCER, J .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1989, 50 (02) :305-307

[8]

Borkar S., 1988, Proceedings. Supercomputing '88 (IEEE Cat. No.88CH2617-9), P330, DOI 10.1109/SUPERC.1988.44670

[9] EXISTENCE AND CONSTRUCTION OF EDGE-DISJOINT PATHS ON EXPANDER GRAPHS [J].

BRODER, AZ ;

FRIEZE, AM ;

UPFAL, E .

SIAM JOURNAL ON COMPUTING, 1994, 23 (05) :976-989

[10]

Broder AZ, 1999, RANDOM STRUCT ALGOR, V14, P87, DOI 10.1002/(SICI)1098-2418(1999010)14:1<87::AID-RSA5>3.0.CO

← 1 2 3 4 →