A New Algorithm for k-Cardinality Assignment Problem

The k-cardinality assignment problem is a generalization of the assignment problem in which a cost matrix and a positive integer k are given and one wants to assign k rows to k columns so that the sum of the corresponding costs is a minimum. M. Dell´ Amico and S. Martello are the first who considered the k-cardinality assignment problem (1997). In 2001, M. Dell´ Amico, A. Lodi and S. Martello considered further specialized efficient algorithm. The object of this paper is to show the k-cardinality assignment problem is solvable by transforming it into a classical assignment problem, and obtain a new algorithm.