A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem

J. Kennington and Zhao-Hua Wang ()
Additional contact information
J. Kennington: Southern Methodist University, Dallas, Texas

Operations Research, 1992, vol. 40, issue 1, 178-187

Abstract: The objective of this study is to develop a shortest augmenting path algorithm for solving the semi-assignment problem and conduct an extensive computational comparison with the best alternative approaches. The algorithm maintains dual feasibility and complementary slackness and works toward satisfying primal feasibility. Effective heuristics arc used to achieve an excellent advanced start, and convergence is assured via the use of the shortest augmenting path procedure using reduced costs for arc lengths. Unlike other algorithms, such as the primal simplex or the auction algorithm, each iteration during the final phase of the procedure (also known as the end-game) achieves one additional assignment. The software implementations of our algorithm are fastest for the semi-assignment problems that we tested. Our dense code is also faster than the best software for assignment problems. In addition, the algorithm has the best polynomial worst-case running time bound that we have seen; and the memory requirements are relatively small.

Keywords: networks/graphs: algorithm for the semi-assignment problem; flow algorithms (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.178 (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:oropre:v:40:y:1992:i:1:p:178-187

Access Statistics for this article

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