The authors review a class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation. All the methods in the class use the notion of •-complementary slackness, and most do not explicitly manipulate any ‘global’ objects such as paths, trees, or cuts. Interestingly, these methods have stimulated a large number of new serial computational complexity results. The authors 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. They show how to implement these methods with serial complexities of O(N3logNC) and O(NAlogNC), respectively. The authors also discuss practical implementation issues and computational experience to date. Finally, they show how to implement •-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.
