The “signature” of a dual feasible basis of the assignment problem is an n-vector whose ith 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.
No takes yet. Share an insight, caveat, or question.
Michel Balinski (1985) studied this question.