Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem
Abstract
An O(n sup 3) heuristic algorithm is described for solving n-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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1976
- Accession Number
- ADA025602
Entities
People
- Nicos Christofides
Organizations
- Carnegie Mellon University