Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations

DOI10.1016/0166-218X(90)90101-HzbMath0693.90093OpenAlexW2009358064MaRDI QIDQ908860

T. W. S. Meyer, T. H. C. Smith, Gerald L. Thompson

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0166-218x(90)90101-h

zbMATH Keywords

reductionLower boundssymmetric travelling salesman2-matching relaxation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonlinear programming (90C30) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Related Items (1)

The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• Nonoptimal Edges for the Symmetric Traveling Salesman Problem
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• A restricted Lagrangean approach to the traveling salesman problem
• An operator theory of parametric programming for the generalized transportation problem: II Rim, cost and bound operators
• An Algorithm for the Traveling Salesman Problem
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• The traveling-salesman problem and minimum spanning trees: Part II

This page was built for publication: Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations