Dual coordinate step methods for linear network flow problems

• DOI: 10.1007/bf01589405
• Publication Date: 2005-04-28T09:09:36Z
• Authors: Dimitri P. Bertsekas; Jonathan Eckstein
• Keywords: Minimum-cost flow problem; Multi-commodity flow problem

We review a class of recently-proposed linear-cost network flow methods which are amenable to parallel implementation. All the methods in the class use the notion of c-complementary slackness, and most do not explicitly manipulate any "global" objects such as paths, trees, or cuts. Interestingly, these methods have also stimulated a large number of new serial computational complexity results. We develop the basic theory of these methods and present two specific methods, the E-relaxation algorithm for the minimum-cost flow problem, and the auction algorithm for assignment problem. We show how to implement these methods with serial complexities of O(N 3 log NC) and O(NA log NC), respectively. We also discuss practical implementation issues and computational experience to date. Finally, we show how to implement e-relaxation in a completely asynchronous, "chaotic" environment in which some processors compute faster than others, some processors communicate faster than others, and there can be arbitrarily large communication delays.