Accession Number:

ADA025602

Title:

Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem

Descriptive Note:

Research rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1976-02-01

Pagination or Media Count:

11.0

Abstract:

An On 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 32. 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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE