Dual coordinate step methods for linear network flow problems |
| |
Authors: | Dimitri P. Bertsekas Jonathan Eckstein |
| |
Affiliation: | (1) Laboratory for Information and Decision Systems and Operations Research Center, Massachusetts Institute of Technology, 02139 Cambridge, MA, USA |
| |
Abstract: | We 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 newserial computational complexity results. We develop the basic theory of these methods and present two specific methods, the-relaxation algorithm for the minimum-cost flow problem, and theauction algorithm for the assignment problem. We show how to implement these methods with serial complexities of O(N3 logNC) and O(NA logNC), respectively. We also discuss practical implementation issues and computational experience to date. Finally, we 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.Supported by Grant NSF-ECS-8217668 and by the Army Research Office under grant DAAL03-86-K-0171. Thanks are due to David Castañon, Paul Tseng, and Jim Orlin for their helpful comments. |
| |
Keywords: | Network flows relaxation distributed algorithms complexity asynchronous algorithms |
本文献已被 SpringerLink 等数据库收录! |
|