Efficient algorithms and codes for k-cardinality assignment problems

Given a cost matrix W and a positive integer k, the k-cardinality assignment problem is to assign k rows to k columns so that the sum of the corresponding costs is a minimum. This generalization of the classical assignment problem is solvable in polynomial time, either by transformation to min-cost flow or through specific algorithms. We consider the algorithm recently proposed by Dell'Amico and Martello for the case where W is dense, and derive, for the case of sparse matrices, an efficient algorithm which includes original heuristic preprocessing techniques. The resulting code is experimentally compared with min-cost flow codes from the literature. Extensive computational tests show that the code is considerably faster, and effectively solves very large sparse and dense instances. © 2001 Elsevier Science B.V.