Accession Number : ADA194028

Title :   Finding Minimum-Cost Circulations by Successive Approximation,

Corporate Author : PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE

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

PDF Url : ADA194028

Report Date : Jul 1987

Pagination or Media Count : 56

Abstract : This document develops a new approach to solving minimum-cost circulation problems. This approach combines methods for solving the maximum flow problem with successive approximation techniques based on cost scaling. The authors measure the accuracy of a solution by the amount that the complementary slackness conditions are violated. They propose a simple minimum-cost circulation algorithm, one version of which runs in O(cu n log(nC)) time on an n-vertex network with integer arc costs of absolute value at most C. By incorporating sophisticated data structures into the algorithm, we obtain a time bound of O(nm log(sq n/m) log(nC)) on a network with m arcs. A slightly different use of our approach shows that a minimum-cost circulation can be computed by solving a sequence of O(n log(nC)) blocking slow problems. A corollary of this result is an O(sq n (log n) log (nC)-time, n-processor parallel minimum cost circulation algorithm. This approach also yields strongly polynomial minimum-cost circulation algorithms. Results provide evidence that the minimum-cost circulation problem is not much harder than the maximum flow problem. It is believed that a suitable implementation of this method will perform extremely well in practice. Keywords: Network flows.

Descriptors :   *LOW COSTS, *NETWORK FLOWS, *COST ANALYSIS, ACCURACY, ALGORITHMS, CIRCULATION, COSTS, DATA BASES, POLYNOMIALS, PROBLEM SOLVING

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE