Signature Methods for the Assignment Problem
Operations Research · 1985 · Volume 33 · Issue 3
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
Enable JavaScript for citation tools and additional paper interactions.