Homework 5

  1. Consider the algorithm ApproxTSP (Algorithm 3.7 in Vazirani, or on page 3 in Mark de Berg's lecture notes). When the edge lengths of the input graph G satisfy the triangle inequality, ApproxTSP gives a 2-approximation. Let c be any constant. Give an example of a graph G where the edge weights do not satisfy the triangle inequality such that ApproxTSP returns a tour of length more than c·OPT, where OPT is the minimum length of any tour for G. (Describing the graph is not sufficient, you should also argue that the algorithm indeed gives a tour of length more than c·OPT.)
    Note that it is not sufficient to argue that the length of the tour is more than c times the length of a minimum-spanning tree, because OPT could be larger than MST.
  2. Consider the TSP problem for complete graphs where all the edges have either weight 1 or weight 2.
  3. Exercise 3.4 (page 34) from Vazirani book.

Otfried Cheong