Signature Methods for the Assignment Problem

Abstract

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.