THE K-CARDINALITY ASSIGNMENT PROBLEM

We consider a generalization of the assignment problem in which an int eger k is given and one wants to assign k rows to k columns so that th e sum of the corresponding costs is a minimum. The problem can be seen as a 2-matroid intersection, hence is solvable in polynomial time; im mediate algorithms for it can be obtained from transformation to min-c ost flow or from classical shortest augmenting path techniques. We int roduce original preprocessing techniques for finding optimal solutions in which g less than or equal to k rows are assigned, for determining rows and columns which must be assigned in an optimal solution and fo r reducing the cost matrix. A specialized primal algorithm is finally presented. The average computational efficiency of the different appro aches is evaluated through computational experiments.