- Published
- 2022-03-01
- Venue
- Operations Research Forum, vol. 3, no. 1
- Cited by
- 1,131
- Open access
- Yes, hybrid
- DOI
- 10.1007/s43069-021-00101-z
Abstract
An O( n 3 ) heuristic algorithm is described for solving d -city travelling salesman problems (TSP) whose cost matrix satisfies the triangularity condition. The algorithm involves as substeps the computation of a shortest spanning tree of the graph G defining the TSP and the finding of a minimum cost perfect matching of a certain induced subgraph of G . A worst-case analysis of this heuristic shows that the ratio of the answer obtained to the optimum TSP solution is strictly less than 3/2. This represents a 50% reduction over the value 2 which was the previously best known such ratio for the performance of other polynomial growth algorithms for the TSP.
Cite this paper
Formatted from the source metadata, not typed by hand. For a whole reference list, use the citation generator or ask your assistant through Find Research.
- APA 7
Christofides, N. (2022). Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. Operations Research Forum, 3(1). https://doi.org/10.1007/s43069-021-00101-z
- MLA 9
Christofides, Nicos. "Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem." Operations Research Forum, vol. 3, no. 1, 2022, https://doi.org/10.1007/s43069-021-00101-z.
- Chicago
Christofides, Nicos. "Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem." Operations Research Forum 3, no. 1 (2022). https://doi.org/10.1007/s43069-021-00101-z.
- GOST
Christofides N. Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem // Operations Research Forum. — 2022. — Vol. 3, № 1. — URL: https://doi.org/10.1007/s43069-021-00101-z
- BibTeX
@article{christofides2022worstcase, title = {{Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem}}, author = {Nicos Christofides}, journal = {Operations Research Forum}, year = {2022}, volume = {3}, number = {1}, doi = {10.1007/s43069-021-00101-z}, url = {https://doi.org/10.1007/s43069-021-00101-z} }- RIS
TY - JOUR AU - Christofides, Nicos TI - Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem JO - Operations Research Forum VL - 3 IS - 1 PY - 2022 DA - 2022/03/01 DO - 10.1007/s43069-021-00101-z UR - https://doi.org/10.1007/s43069-021-00101-z ER -