Abstract
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.
Keywords
Travelling salesman problemHeuristicCombinatoricsMathematicsMathematical optimizationComputationMatching (statistics)Matrix (chemical analysis)Minimum spanning treeSteiner tree problemGraphComputer scienceAlgorithm
Affiliated Institutions
Related Publications
Ant system: optimization by a colony of cooperating agents
An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). We propose it as a viable new approach...
Ant colony system: a cooperative learning approach to the traveling salesman problem
This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents calle...
A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems
The combination of local search heuristics and genetic algorithms is a promising approach for finding near-optimum solutions to the traveling salesman problem (TSP). An approach...
Computer Solutions of the Traveling Salesman Problem
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer. The first produces guaranteed optimal solu...
Partitioning Sparse Matrices with Eigenvectors of Graphs
The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An ...
Publication Info
- Year
- 2022
- Type
- article
- Volume
- 3
- Issue
- 1
- Citations
- 1120
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1120
OpenAlex
Cite This
Nicos Christofides
(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
Identifiers
- DOI
- 10.1007/s43069-021-00101-z