Dual coordinate step methods for linear network flow problems

Dimitri P. Bertsekas, Jonathan Eckstein

Research output: Contribution to journalArticle

49 Scopus citations

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 new serial 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 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, "chaotic" environment in which some processors compute faster than others, some processors communicate faster than others, and there can be arbitrarily large communication delays.

Original languageEnglish (US)
Pages (from-to)203-243
Number of pages41
JournalMathematical Programming
Volume42
Issue number1-3
DOIs
StatePublished - Apr 1 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Network flows
  • asynchronous algorithms
  • complexity
  • distributed algorithms
  • relaxation

Fingerprint Dive into the research topics of 'Dual coordinate step methods for linear network flow problems'. Together they form a unique fingerprint.

  • Cite this