Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost

Katta G. Murty
Additional contact information
Katta G. Murty: University of California, Berkeley, California

Operations Research, 1968, vol. 16, issue 3, 682-687

Abstract: The Hungarian method gives an efficient algorithm for finding the minimal cost assignment. However, in some cases it may be useful to determine the second minimal assignment (i.e., the best assignment after excluding the minimal cost assignment) and in general the k th minimal assignment for k = 1, 2, …. These things can easily be determined if all the assignments can be arranged as a sequence in increasing order of cost. This paper describes an efficient algorithm for such a ranking of all the assignments. The maximum computational effort required to generate an additional assignment in the sequence is that of solving at most ( n − 1) different assignment problems, one each of sizes 2, 3, …, n .

Date: 1968
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.16.3.682 (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:16:y:1968:i:3:p:682-687

Access Statistics for this article

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