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 matrices; min-sum linear assignment; Primal-dual algorithms; randomly-generated test problems; Shortest Augmenting Path

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)

Related Items

A genuinely polynomial primal simplex algorithm for the assignment problem, Generating, scheduling and rostering of shift crew-duties: applications at the Hong Kong international airport, A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Algorithms and codes for dense assignment problems: The state of the art, Linear and semi-assignment problems: A core oriented approach, A goal programming model for crew duties generation

Uses Software

• Algorithm 548

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item