The Auction Algorithm for Assignment and Other Network Flow Problems: A Tutorial

Dimitri P. Bertsekas
Additional contact information
Dimitri P. Bertsekas: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Interfaces, 1990, vol. 20, issue 4, 133-149

Abstract: The auction algorithm is an intuitive method for solving the classical assignment problem. It outperforms substantially its main competitors for important types of problems, both in theory and in practice and is also naturally well suited for parallel computation. I derive the algorithm from first principles, explain its computational properties, and discuss its extensions to transportation and transshipment problems.

Keywords: programming: mathematical; networks/graphs (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/inte.20.4.133 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orinte:v:20:y:1990:i:4:p:133-149

Access Statistics for this article

More articles in Interfaces from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().