Solving the Assignment Problem by Relaxation

Ming S. Hung and Walter O. Rom
Additional contact information
Ming S. Hung: Kent State University, Kent, Ohio
Walter O. Rom: Cleveland State University, Cleveland, Ohio

Operations Research, 1980, vol. 28, issue 4, 969-982

Abstract: This paper presents a new algorithm for solving the assignment problem. The algorithm is based on a scheme of relaxing the given problem into a series of simple network flow (transportation) problems for each of which an optimal solution can be easily obtained. The algorithm is thus seen to be able to take advantage of the nice properties in both the primal and the dual approaches for the assignment problem. The computational bound for the algorithm is shown to be 0( n 3 ) and the average computation time is better than most of the specialized assignment algorithms.

Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.28.4.969 (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:28:y:1980:i:4:p:969-982

Access Statistics for this article

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