Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem

The Held-Karp heuristic for the Traveling Salesman Problem (TSP) has in practice provided near-optimal lower bounds on the cost of solutions to the TSP. We analyze the structure of Held-Karp solutions in order to shed light on their quality.

Bibliographic Details
Main Author:	Williamson, D.P.
Published:	2023
Online Access:	https://hdl.handle.net/1721.1/149691

Similar Items

On the spacefilling curve heuristic for the Eculidean traveling salesman problem
by: Bertsimas, Dimitris., et al.
Published: (2009)

New heuristic function in ant colony system for the travelling salesman problem
by: Alobaedy, Mustafa Muwafak, et al.
Published: (2012)

Performance evaluation of heuristic methods in solving symmetric travelling salesman problems
by: Lim, Yai-Fung, et al.
Published: (2016)

A comparative study of heuristic methods to solve Traveling Salesman Problem (TPS)
by: Lim, Yai Fung, et al.
Published: (2011)

An algorithm for the traveling salesman problem,
by: Little, John D. C.
Published: (2009)

Probabilistic Traveling Salesman Problems
by: Jaillet, Patrick
Published: (2005)

Traveling salesman path problems
by: Lam, Fumei
Published: (2006)

The Travelling Salesman Problem and Related Problems
by: Gavish, Bezalel, et al.
Published: (2004)

An adaptive large neighborhood search heuristic for the flying sidekick traveling salesman problem with multiple drops
by: Mara, Setyo Tri Windras, et al.
Published: (2022)

Computational Complexity and the Traveling Salesman Problem
by: Johnson, David, et al.
Published: (2023)

Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
by: Paul, Alice, et al.
Published: (2021)

Trajectory Stability in the Traveling Salesman Problem
by: Sánchez, Sergio, et al.
Published: (2018)

Convergent Duality for the Traveling Salesman Problem
by: Shapiro, Jeremy F., 1939-
Published: (2004)

Algoritma polinomial dan traveling salesman problem
by: , WIDYASTUTI, Naniek, et al.
Published: (1999)

The Traveling Salesman Problem for Systems with Dynamic Constraints
by: Adler, Aviv
Published: (2023)

On semidefinite programming relaxations of the traveling salesman problem
by: De Klerk, Etienne., et al.
Published: (2009)

On the Stochastic Travelling Salesman problem for the Dubin's vehicle
by: Itani, Sleiman M
Published: (2007)

Online traveling salesman problems with rejection options
by: Jaillet, Patrick, et al.
Published: (2015)

Online Traveling Salesman Problems with Service Flexibility
by: Jaillet, Patrick, et al.
Published: (2011)

The Traveling Salesman Problem and orienteering for kinodynamic vehicles
by: Adler, Aviv
Published: (2018)

Two traveling salesman facility location problems
Published: (2003)

An arc flow formulation for the travelling salesman problem
by: Claus, A.
Published: (2009)

Simulated annealing with probabilistic analysis for solving traveling salesman problems
by: Hong, Pei Yee, et al.
Published: (2013)

Swarm intelligence algorithms’ solutions to the travelling salesman’s problem
by: Odili, Julius Beneoluchi, et al.
Published: (2020)

Graph convolutional neural networks for the travelling salesman problem
by: Joshi, Chaitanya Krishna
Published: (2019)

Probabilistic analysis of the 1-tree relaxation for the Eculidean traveling salesman problem
by: Goemans, Michel X., et al.
Published: (2009)

Genetic algorithm to optimize routing problem modelled as the travelling salesman problem
by: Muhammad Azrul Faiz , Nor Adzmi
Published: (2013)

Memetic framework with adaptive meme pool for the travelling salesman problem
by: Zeng, Yuntao
Published: (2023)

An improved tabu search for solving symmetric traveling salesman problems
by: Lim, Yai Fung, et al.
Published: (2011)

Modified reactive tabu search for the symmetric traveling salesman problems
by: Lim, Yai Fung, et al.
Published: (2013)

Tutorials on African Buffalo Optimization for Solving the Travelling Salesman Problem
by: Odili, Julius Beneoluchi, et al.
Published: (2017)

Solving the Traveling Salesman’s Problem using the African Buffalo Optimization
by: Odili, Julius Beneoluchi, et al.
Published: (2016)

Special cases of traveling salesman and repairman problems with time windows
Published: (2003)

Algorithms for a scheduling application of the Asymmetric Traveling Salesman Problem.
by: Kanellakis, Paris C
Published: (2005)

Bee colony optimisation of the travelling salesman problem in light rail systems
by: Wang, Chen, et al.
Published: (2019)

Enhanced selection method for genetic algorithm to solve traveling salesman problem
by: Jubeir, Mohammed, et al.
Published: (2017)

A GPU accelerated parallel genetic algorithm for the traveling salesman problem
by: Binjubier, Mohammed, et al.
Published: (2024)

An optimization framework of K-means clustering and metaheuristic for traveling salesman problem
by: Wang, Benquan
Published: (2021)

Optimization of traveling salesman problem with Google app engine project report
by: Lin, Runhui.
Published: (2011)