AN AUCTION ALGORITHM FOR THE MAX-FLOW PROBLEM

被引：18

作者：

BERTSEKAS, DP

机构：

[1] Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts

来源：

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS | 1995年 / 87卷 / 01期

关键词：

NETWORK OPTIMIZATION; MAX-FLOW PROBLEMS; AUCTION ALGORITHMS; PREFLOW-PUSH ALGORITHMS;

D O I：

10.1007/BF02192042

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We propose a new algorithm for the max-flow problem. It consists of a sequence of augmentations along paths constructed by an auction-like algorithm. These paths are not necessarily shortest, that is, they need not contain a minimum number of arcs. However, they can be found typically with much less computation than the shortest augmenting paths used by competing methods. Our algorithm outperforms these latter methods as well as state-of-the-art preflow-push algorithms by a very large margin in tests with standard randomly generated problems.

引用

页码：69 / 101

页数：33

共 29 条

[1]

Ahuja R.K., 1989, HDB OPERATIONS RES M, DOI 10.1016/S0927-0507(89)01005-4

[2] A FAST AND SIMPLE ALGORITHM FOR THE MAXIMUM FLOW PROBLEM [J].

AHUJA, RK ;

ORLIN, JB .

OPERATIONS RESEARCH, 1989, 37 (05) :748-759

[3]

ANDERSON RJ, 1993, ALGORITHMS NETWORK F, P1

[4]

[Anonymous], 1992, COMPUT OPTIM APPL

[5]

Bertsekas D.P., 1991, LINEAR NETWORK OPTIM

[6]

Bertsekas D.P., 1979, DISTRIBUTED ALGORITH

[7]

Bertsekas D. P., 1988, ANN OPER RES, V13, P127

[8] AN AUCTION ALGORITHM FOR SHORTEST PATHS [J].

Bertsekas, Dimitri P. .

SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (04) :425-447

[9]

BERTSEKAS DP, 1994, LARGE SCALE OPTIMIZATION: STATE OF THE ART, P26

[10]

BERTSEKAS DP, 1992, LIDSP2107 MIT LAB IN

← 1 2 3 →