Finding minimum-cost circulations by successive approximation

Finding minimum-cost circulations by successive approximation

0.00 Avg rating0 Votes
Article ID: iaor1991316
Country: United States
Volume: 15
Start Page Number: 430
End Page Number: 466
Publication Date: Jun 1990
Journal: Mathematics of Operations Research
Authors: ,
Keywords: computational analysis
Abstract:

The authors develop a new approach to solving minimum-cost circulation problems. The present 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(n3log(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, the authors obtain a time bound of O(nmlog(n2/m)log(nC)) on a network with m arcs. A slightly different use of the present approach shows that a minimum-cost circulation can be computed by solving a sequence of O(nlog(nC)) blocking flow problems. A corollary of this result is an O(n2(logn)log(nC))-time, m-processor parallel minimum-cost circulation algorithm. The present approach also yields strongly polynomial minimum-cost circulation algorithms. The results provide evidence that the minimum-cost circulation problem is not much harder than the maximum flow problem. The authors believe that a suitable implementation of the present method will perform extremely well in practice.

Reviews

Required fields are marked *. Your email address will not be published.