Primal-dual algorithms for the assignment problem (Q1095790): Difference between revisions
From MaRDI portal
Latest revision as of 13:40, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Primal-dual algorithms for the assignment problem |
scientific article |
Statements
Primal-dual algorithms for the assignment problem (English)
0 references
1987
0 references
Primal-dual algorithms for the min-sum linear assignment problem are summarized. Procedures obtained by combining the Hungarian and Shortest Augmenting Path methods for complete and sparse cost matrices are presented. A new agorithm is proposed for the complete case, which transforms the complete cost matrix into a sparse one, solves the sparse problem and checks the optimality of the solution found with respect to the original problem. Extensive computational results on different classes of randomly-generated test problems are presented both for complete and sparse cost matrices.
0 references
Primal-dual algorithms
0 references
min-sum linear assignment
0 references
Shortest Augmenting Path
0 references
complete and sparse cost matrices
0 references
randomly-generated test problems
0 references