The K-Cardinality Assignment Problem.

We consider a generalization of the assignment problem in which an integer k is given and onewants to assign k rows to k columns so that the sum of the corresponding costs is a minimum.The problem can be seen as a 2-matroid intersection, hence is solvable in polynomial time; immediatealgorithms for it can be obtained from transformation to min-cost flow or from classicalshortest augmenting path techniques. We introduce original preprocessing techniques for findingoptimal solutions in which g< k rows are assigned, for determining rows and columns whichmust be assigned in an optimal solution and for reducing the cost matrix. A specialized primalalgorithm is finally presented. The average computational efficiency of the different approachesis evaluated through computational experiments.