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

DOI10.1007/BF01585505zbMath0285.90055MaRDI QIDQ4772973

Jakob Krarup, Keld Helbig Hansen

Publication date: 1974

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

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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