Accession Number : ADA192727

Title :   Finding Minimum-Cost Circulations by Canceling Negative Cycles.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Goldberg, Andrew V ; Tarjan, Robert E

PDF Url : ADA192727

Report Date : Jul 1987

Pagination or Media Count : 20

Abstract : A classical algorithm for finding a minimum cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in 0(nm(log n)min(log(nC), mlogn)) time on a network of n vertices, m arcs, and arc costs of maximum absolute value C. This bound is comparable to those of the fastest previously known algorithms. Keywords: Network flows, Minimum cost flow, Combinatorial optimization.

Descriptors :   *ALGORITHMS, *NETWORK FLOWS, *LOW COSTS, CIRCULATION, COMBINATORIAL ANALYSIS, COSTS, CYCLES, DYNAMICS, FLOW, OPTIMIZATION, POLYNOMIALS, RESIDUALS, TREES, VARIATIONS, ITERATIONS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE