
Accession Number : ADA194028
Title : Finding MinimumCost 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 minimumcost 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 minimumcost circulation algorithm, one version of which runs in O(cu n log(nC)) time on an nvertex 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 minimumcost 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, nprocessor parallel minimum cost circulation algorithm. This approach also yields strongly polynomial minimumcost circulation algorithms. Results provide evidence that the minimumcost 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