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(N3 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.
|Original language||English (US)|
|Number of pages||41|
|Journal||Mathematical Programming, Series B|
|State||Published - Nov 1 1988|
All Science Journal Classification (ASJC) codes