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

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

Cited in

(19)

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

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)