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.
   • Prove that the TSP problem is still NP-hard for these graphs.
   • Prove that these edge weights satisfy the triangle inequality.
   • Since the triangle inequality holds, algorithm ApproxTSP gives a 2-approximation for graphs where the edge weights are 1 or 2. Someone conjectures that for these special graphs, the algorithm in fact always gives a (3/2)-approximation. Prove or disprove this conjecture.
3. Exercise 3.4 (page 34) from Vazirani book.