How to compute least infeasible flows

被引：10

作者：

McCormick, ST ^{[1
]}

机构：

[1] UNIV GRENOBLE 1, IMAG, LAB ARTEMIS, GRENOBLE, FRANCE

来源：

MATHEMATICAL PROGRAMMING | 1997年 / 78卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

network flows; min-cost flow; cut canceling;

D O I：

10.1007/BF02614370

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

It is well-known how to use maximum flow to decide when a flow problem with demands, lower bounds, and upper bounds is infeasible. Less well-known is how to compute a flow that is least infeasible. This paper considers many possible ways to define ''least infeasible'' and shows how to compute optimal flows for each definition. For each definition it also gives a dual characterization in terms of cuts, a polynomial routine for recognizing that type of least infeasible flow, and relates that definition to dual cut canceling min-cost flow network algorithms. (C) 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

引用

页码：179 / 194

页数：16

共 30 条

[11] A FAST PARAMETRIC MAXIMUM FLOW ALGORITHM AND APPLICATIONS [J].

GALLO, G ;

GRIGORIADIS, MD ;

TARJAN, RE .

SIAM JOURNAL ON COMPUTING, 1989, 18 (01) :30-55

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

GOLDBERG, AV ;

TARJAN, RE .

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

[13]

GOLDBERG AV, 1992, STANCS921429 STANF U

[14]

Greenberg H.J., 1987, IMA J MATH MANAGEMEN, V1, P99

[15]

Greenberg H.J., 1988, IMA J MATH MANAGEMEN, V2, P39

[16]

GREENBERG HJ, 1993, UNPUB ANN MATH ARTIF

[17] THE MINIMUM COST FLOW PROBLEM - A UNIFYING APPROACH TO DUAL ALGORITHMS AND A NEW TREE-SEARCH ALGORITHM [J].

HASSIN, R .

MATHEMATICAL PROGRAMMING, 1983, 25 (02) :228-239

[18] ALGORITHMS FOR THE MINIMUM COST CIRCULATION PROBLEM BASED ON MAXIMIZING THE MEAN IMPROVEMENT [J].

HASSIN, R .

OPERATIONS RESEARCH LETTERS, 1992, 12 (04) :227-233

[19]

Hoffman AJ, 1960, Sypmosium Applied Mathematics, V10, P113

[20] A NEW SCALING ALGORITHM FOR THE MAXIMUM MEAN CUT PROBLEM [J].

IWANO, K ;

MISONO, S ;

TEZUKA, S ;

FUJISHIGE, S .

ALGORITHMICA, 1994, 11 (03) :243-255

← 1 2 3 →