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 [Formula: see text] , [Formula: see text] . Here we are interested in computing the sequence of all k-assignments, [Formula: see text] . By applying the algorithm of Gassner and Klinz (2010) for the parametric assignment problem one can compute in time [Formula: see text] the set of k-assignments for those integers [Formula: see text] which refer to essential terms of the full characteristic maxpolynomial [Formula: see text] of the corresponding max-plus weight matrix W. We show that [Formula: see text] is in full canonical form, which implies that the remaining k-assignments refer to semi-essential terms of [Formula: see text] . This property enables us to efficiently compute in time [Formula: see text] 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 [Formula: see text] , which is the best known time for this problem.