Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem 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 rati...