On dual solutions of the linear assignment problem

DOI10.1016/0377-2217(85)90310-8zbMath0557.90066OpenAlexW2028068470MaRDI QIDQ761971

A. Volgenant, V. van Gijlswijk, G. de Leve, G. A. P. Kindervater

Publication date: 1985

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(85)90310-8

zbMATH Keywords

traveling salesmandual solutionslinear assignmentshortest path algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• Solving symmetric vehicle routing problems asymmetrically
• An approach for solving a class of transportation scheduling problems
• Network flow, transportation and scheduling. Theory and algorithms
• An operator theory of parametric programming for the transportation problem-I
• Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem
• A restricted Lagrangean approach to the traveling salesman problem
• An exact branch-and-bound procedure for the quadratic-assignment problem
• Technical Note—Bounds for the Travelling-Salesman Problem
• On some techniques useful for solution of transportation network problems

Related Items (12)

Improving Christofides' lower bound for the traveling salesman problem ⋮ A simple dual algorithm for the generalised assignment problem ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem ⋮ Better assignment lower bounds for the Euclidean traveling salesman problem ⋮ A note on dual solutions of the assignment problem in connection with the traveling salesman problem ⋮ A labeling algorithm for the sensitivity ranges of the assignment problem ⋮ An additive bounding procedure for the asymmetric travelling salesman problem ⋮ A reduction approach to the repeated assignment problem ⋮ An addendum on: ``Sensitivity analysis of the optimal assignment ⋮ Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems ⋮ Solving some lexicographic multi-objective combinatorial problems

This page was built for publication: On dual solutions of the linear assignment problem