CS 46 Comprehensive Final Exam is scheduled for Friday, 8 May 9am-12n in Sci 264.

Due: Wednesday, April 29

1. Write solutions to: 6.4.2, c7.4.7, c7.4.8, c7.4.9 where c7.4.x is given below.
   
   
   
   c7.4.7. We want to design an approximation algorithm for instances of the Traveling Salesman Problem (TSP) that satisfy the triangle inequality (tri). We will do this using what is called the "closest point heuristic". Given an instance of TSP that satisfies the triangle inequality, pick any vertex and imagine a trivial cycle from that vertex to itself. Call this cycle, C. Now execute the loop below until all vertices are on C. loop pick a vertex u not in C whose distance to a vertex in C is minimal. let v be the vertex in C such that (u, v) is a minimal cost edge of all edges from vertices outside of C to vertices in C. let C' be the cycle C extended by puting u just after v in C. replace C by C' end loop
   
   Show that for TSP instances that satisfy the triangle inequality,this returns a cycle whose cost is not more than twice the optimal solution to the given TSP instance. Argue that this is a poly-time algorithm.
   Hint: Consider the minimal cost spanning tree problem. What is the relationship between c(MST), c(min-TSP), and c(2MST). Twice around an MST visits every vertex twice. Maybe you can use triangle inequality to cut out some vertices and come up with a pretty-good TSP tour.
   
   c7.4.8. a) Show that the Traveling Saleman Problem (TSP) remains NP-complete even when the distances satisfy the triangle inequality.
   b) For any instance I of TSP, show a poly-time transformation into another instance I', such that the cost function of I' satisfies the triangle inequality and such that I' has has the same set of optimal tours as I. Combining this with c7.4.7, you might think that we have a contradiction to the assertion on page 339 that TSP is inapproximable. Why is there no contradiction?
   
   c7.4.9. Consider the Bin Packing problem shown to be NP-complete in exercise 7.3.4h. The optimization version is: What is the smallest number of K-size bins that can contain all of the multi-set A. (a multi-set allows repetition). There is a heuristic called 'first-fit'. Guess what it is and tell me (with supporting argument) how good an approximation first-fit gives us.