Computing the sequence of k -cardinality assignments.

The k -cardinality assignment ( k -assignment, for short) problem asks for finding a minimal (maximal) weight of a matching of cardinality k in a weighted bipartite graph K n , n , k ≤ n . Here we are interested in computing the sequence of all k -assignments, k = 1 , … , n . By applying the algorithm of Gassner and Klinz (2010) for the parametric assignment problem one can compute in time O ( n 3 ) the set of k -assignments for those integers k ≤ n which refer to essential terms of the full characteristic maxpolynomial χ ¯ W ( x ) of the corresponding max-plus weight matrix W . We show that χ ¯ W ( x ) is in full canonical form, which implies that the remaining k -assignments refer to semi-essential terms of χ ¯ W ( x ) . This property enables us to efficiently compute in time O ( n 2 ) all the remaining k -assignments out of the already computed essential k -assignments. It follows that time complexity for computing the sequence of all k -cardinality assignments is O ( n 3 ) , which is the best known time for this problem.