@techreport{ae3cb15b43fc4fb29aecbdb0f899b3cf,

title = "Computing the sequence of $k$-cardinality assignments",

abstract = " The k-cardinality assignment problem asks for finding a maximal (minimal) weight of a matching of cardinality k in a weighted bipartite graph Kn,n, k≤n. The algorithm of Gassner and Klinz from 2010 for the parametric assignment problem computes in time O(n3) the set of k-cardinality assignments for those integers k≤n which refer to {"}essential{"} terms of a corresponding maxpolynomial. We show here that one can extend this algorithm and compute in a second stage the other {"}semi-essential{"} terms in time O(n2), which results in a time complexity of O(n3) for the whole sequence of k=1,...,n-cardinality assignments. The more there are assignments left to be computed at the second stage the faster the two-stage algorithm runs. In general, however, there is no benefit for this two-stage algorithm on the existing algorithms, e.g. the simpler network flow algorithm based on the successive shortest path algorithm which also computes all the k-cardinality assignments in time O(n3)",

keywords = "math.OC, cs.DS",

author = "Amnon Rosenmann",

note = "19 pages",

year = "2021",

month = apr,

day = "8",

language = "English",

series = "arXiv.org e-Print archive",

publisher = "Cornell University Library",

type = "WorkingPaper",

institution = "Cornell University Library",

}