Signature Methods for the Assignment Problem

Michel Balinski

Operations Research, 1985, vol. 33, issue 3, 527-536

Abstract: The “signature” of a dual feasible basis of the assignment problem is an n -vector whose i th component is the number of nonbasic activities of type ( i , j ). This paper uses signatures to describe a method for finding optimal assignments that terminates in at most ( n − 1)( n − 2)/2 pivot steps and takes at most O ( n 3 ) work.

Keywords: 432 bipartite matching; 481 algorithm for assignment problem; 637 assignment problem (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.3.527 (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:33:y:1985:i:3:p:527-536

Access Statistics for this article

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