A NATURAL RANDOMIZATION STRATEGY FOR MULTICOMMODITY FLOW AND RELATED ALGORITHMS

被引：16

作者：

GOLDBERG, AV

机构：

[1] Department of Computer Science, Stanford University, Stanford

来源：

INFORMATION PROCESSING LETTERS | 1992年 / 42卷 / 05期

基金：

美国国家科学基金会;

关键词：

ALGORITHMS; NETWORK FLOWS; MULTICOMMODITY FLOWS;

D O I：

10.1016/0020-0190(92)90032-Q

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the approximation algorithm of Leighton et al. (1991) for the multicommodity flow problem. We give a more natural randomization strategy that is simpler and results in a better running time. This strategy also applies to several related algorithms.

引用

页码：249 / 256

页数：8

共 14 条

[1]

AHUJA RK, 1988, STANCS881227 STANF U

[2] FINDING MINIMUM-COST CIRCULATIONS BY SUCCESSIVE APPROXIMATION [J].

GOLDBERG, AV ;

TARJAN, RE .

MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (03) :430-466

[3]

GOLDBERG AV, 1987, 19TH P ACM S THEOR C, P7

[4]

GRIGORIADIS MD, 1991, DCSTR273 RUTG U DEPT

[5] A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].

KARMARKAR, N .

COMBINATORICA, 1984, 4 (04) :373-395

[6]

KLEIN P, 1991, 961 CORN U SCH ORIE

[7]

LEIGHTON T, 1991, 23ST P ANN ACM S THE

[8]

ORLIN JB, 1988, 20TH P ACM S THEOR C, P377

[9]

PLOTKIN SA, 1991, IN PRESS 32ND P IEEE

[10] THE MAXIMUM CONCURRENT FLOW PROBLEM [J].

SHAHROKHI, F ;

MATULA, DW .

JOURNAL OF THE ACM, 1990, 37 (02) :318-334

← 1 2 →