Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem

DOI10.1007/BF01585505zbMATH Open0285.90055MaRDI QIDQ4772973FDOQ4772973

Authors: Keld Helbig Hansen, Jakob Krarup 

Publication date: 1974

Published in: Mathematical Programming (Search for Journal in Brave)

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• A note on two problems in connexion with graphs
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Increasing the efficiency of quicksort

Cited In (19)

• Integer programming approaches to the travelling salesman problem
• The seriation problem and the travelling salesman problem
• Using cutting planes to solve the symmetric Travelling Salesman problem
• A restricted Lagrangean approach to the traveling salesman problem
• Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem
• New lower bounds for the symmetric travelling salesman problem
• The traveling salesman problem: An overview of exact and approximate algorithms
• The traveling salesman problem: A duality approach
• Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies
• Lineare Charakterisierungen von Travelling Salesman Problemen
• Estimating the Held-Karp lower bound for the geometric TSP
• Heuristically guided algorithm for k-parity matroid problems
• Solving large-scale TSP using a fast wedging insertion partitioning approach
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• How to find Steiner minimal trees in Euclidean \(d\)-space
• Probabilistic analysis of solving the assignment problem for the traveling salesman problem
• Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Algorithms for updating minimal spanning trees

This page was built for publication: Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4772973)