On dual solutions of the linear assignment problem
From MaRDI portal
The linear assignment problem (LAP) which is a relaxation of many cominatorial problems such as the traveling salesman problem, delivery and school bus problems, vehicle scheduling problems, the quadratic assignment problem, is considered and a shortest path algorithm is used to compute different dual solutions of the LAP. Two applications in the context of the traveling salesman problem are proposed.
Recommendations
- Linear assignment procedures
- A sequential dual simplex algorithm for the linear assignment problem
- scientific article; zbMATH DE number 3989103
- A note on dual solutions of the assignment problem in connection with the traveling salesman problem
- A shortest augmenting path algorithm for dense and sparse linear assignment problems
Cites work
- A restricted Lagrangean approach to the traveling salesman problem
- An approach for solving a class of transportation scheduling problems
- An exact branch-and-bound procedure for the quadratic-assignment problem
- An operator theory of parametric programming for the transportation problem-I
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3583204 (Why is no real title available?)
- scientific article; zbMATH DE number 3435247 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- Network flow, transportation and scheduling. Theory and algorithms
- On some techniques useful for solution of transportation network problems
- Solving symmetric vehicle routing problems asymmetrically
- Technical Note—Bounds for the Travelling-Salesman Problem
- Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem
- The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
Cited in
(19)- A sequential dual simplex algorithm for the linear assignment problem
- Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem
- An additive bounding procedure for the asymmetric travelling salesman problem
- A simple dual algorithm for the generalised assignment problem
- Solving some lexicographic multi-objective combinatorial problems
- Linear assignment procedures
- Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems
- The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
- An addendum on: ``Sensitivity analysis of the optimal assignment
- scientific article; zbMATH DE number 3883952 (Why is no real title available?)
- scientific article; zbMATH DE number 4167859 (Why is no real title available?)
- Improving Christofides' lower bound for the traveling salesman problem
- Better assignment lower bounds for the Euclidean traveling salesman problem
- scientific article; zbMATH DE number 4195700 (Why is no real title available?)
- A reduction approach to the repeated assignment problem
- A labeling algorithm for the sensitivity ranges of the assignment problem
- Computation of lower tolerances of combinatorial bottleneck problems
- Extending the definition of single and set tolerances
- A note on dual solutions of the assignment problem in connection with the traveling salesman problem
This page was built for publication: On dual solutions of the linear assignment problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q761971)
