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.
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149691 |
| _version_ | 1826191468503498752 |
|---|---|
| author | Williamson, D.P. |
| author_facet | Williamson, D.P. |
| author_sort | Williamson, D.P. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:56:20Z |
| id | mit-1721.1/149691 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:56:20Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1496912023-03-30T04:16:12Z Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem Williamson, D.P. 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. 2023-03-29T15:16:52Z 2023-03-29T15:16:52Z 1990-06 https://hdl.handle.net/1721.1/149691 22135051 MIT-LCS-TR-479 application/pdf |
| spellingShingle | Williamson, D.P. Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem |
| title | Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem |
| title_full | Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem |
| title_fullStr | Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem |
| title_full_unstemmed | Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem |
| title_short | Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem |
| title_sort | analysis of the held karp heuristic for the traveling salesman problem |
| url | https://hdl.handle.net/1721.1/149691 |
| work_keys_str_mv | AT williamsondp analysisoftheheldkarpheuristicforthetravelingsalesmanproblem |