Research output: Contribution to journalConference articlepeer-review

33 Scopus citations


Relaxation methods for optimal network flow problems resemble classical coordinate descent, Jacobi, and Gauss-Seidel methods for solving unconstrained nonlinear optimization problems or systems of nonlinear equations. For problems with linear arc costs, relaxation methods have outperformed by a substantial margin the classical primal simplex and primal-dual methods on standard benchmark problems. However in these methods it is sometimes necessary to change the prices of several nodes as a group in addition to carrying out pure relaxation steps. As a result global node price information is needed occasionally, and distributed implementation becomes somewhat complicated. A distributed algorithm for solving the classical linear cost assignment problem is described. It uses exclusively pure relaxation steps whereby the prices of sources and sinks are changed individually on the basis of only local (neighbor) node price information. The algorithm can be implemented in an asynchronous (chaotic) manner, and seems quite efficient for problems with a small arc cost range.

Original languageEnglish (US)
Pages (from-to)1703-1704
Number of pages2
JournalProceedings of the IEEE Conference on Decision and Control
StatePublished - 1985
Externally publishedYes

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'DISTRIBUTED ASYNCHRONOUS RELAXATION ALGORITHM FOR THE ASSIGNMENT PROBLEM.'. Together they form a unique fingerprint.

Cite this