
Accession Number : ADA194027
Title : Finding MinimumCost Circulations by Canceling Negative Cycles,
Corporate Author : PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
Personal Author(s) : Goldberg, Andrew V ; Tarjan, Robert E
PDF Url : ADA194027
Report Date : Jul 1987
Pagination or Media Count : 20
Abstract : A classical algorithm for finding a minimumcost 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 O(nm(log n) min log (nC), m log n) 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.
Descriptors : *LOW COSTS, *NETWORK FLOWS, *COST ANALYSIS, ALGORITHMS, CIRCULATION, CYCLES, DYNAMICS, POLYNOMIALS, RESIDUALS, TREES, VARIATIONS, ITERATIONS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE