Dual coordinate step methods for linear network flow problems

We review a class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation. We develop the basic theory of these methods and present two specific methods, the ε-relaxation algorithm for the minimum-cost flow problem, and the auction algorithm for the assignment problem. We show how to implement these methods with serial complexities of O(N³ 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 ε-relaxation in a completely asynchronous environment in which some processors compute faster than others, some processors communicate faster than others, and there can be arbitrarily large communication delays.