Efficient Algorithms and Codes for k-Cardinality Assignment Problems

Given a cost matrix W and a positive integer k, the k-cardinalityassignment problem is to assign k rows to k columns so thatthe 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 codeis considerably faster, and effectively solves very large sparse and dense instances.