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.
The K-Cardinality Assignment Problem / Dell'Amico, Mauro; S., Martello. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 76:(1996), pp. 103-121.
The K-Cardinality Assignment Problem.
DELL'AMICO, Mauro;
1996
Abstract
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.Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris