Lecture Notes for CS 512, Algorithm Design

29 March 2000, The Traveling Salesman Problem

1. a hamiltonian cycle over an undirected graph

2. the tsp - find a minimal hamiltonian cycle over a complete, nonnegative integer weighted, undirected graph

3. the tsp is np complete

4. the shortest distance between two points - the triangle inequality

5. the tsp approximation algorithm

   1. form a mst from an arbitrary root in G

   2. the hamiltonian cycle is a pre-order walk of the tree

   3. the ratio bound is 2

      1. weight of optimal tour is at least weight of the mst

      2. weight of post-order traversal is twice the weight of the mst

      3. weight of suboptimal tour is at most weight of post-order traversal

6. without the triangle inequality, there seems to be no approximation algorithm

   1. suppose aprx-tsp() has a ratio bound of r

   2. let G = (V, E) be an instance of the hamiltonian cycle problem

   3. define the complete graph G' = (V, E') such that the edges in G have weight 1 and all other edges have weight r|V| + 1

   4. if G has a hamiltonian cycle, the tsp has a solution

   5. if the tsp has a solution, it must be a hamiltionian cycle in G

7. postprocessing approximate tsp results to get less sub-optimal solutions

   1. k-opt - replace k edges with new edges

This page last modified on 3 April 2000.