Primal-dual algorithms for the assignment problem

DOI10.1016/0166-218X(87)90016-3zbMath0632.90041MaRDI QIDQ1095790

Paolo Toth, Giorgio Carpaneto

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

complete and sparse cost matricesmin-sum linear assignmentPrimal-dual algorithmsrandomly-generated test problemsShortest Augmenting Path

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items

Generating, scheduling and rostering of shift crew-duties: applications at the Hong Kong international airport, Classes of linear programs solvable by coordinate-wise minimization, On the initialization methods of an exterior point algorithm for the assignment problem, Algorithms and codes for dense assignment problems: The state of the art, A heuristic algorithm based on multi-assignment procedures for nurse scheduling, A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems, A genuinely polynomial primal simplex algorithm for the assignment problem, A goal programming model for crew duties generation, Linear and semi-assignment problems: A core oriented approach, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems

Uses Software

• Algorithm 548

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• Algorithm for the solution of the assignment problem for sparse matrices
• A new algorithm for the assignment problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Technical Note—A “Hard” Assignment Problem
• The alternating basis algorithm for assignment problems
• Implementation and Testing of a Primal-Dual Algorithm for the Assignment Problem
• On some techniques useful for solution of transportation network problems