Approximation Algorithms Spring 2014 MP Johnson Homework 2 Due: 7am, Tuesday 2/25/14 Solutions must be written up in Latex and submitted by email. Here is a bare-bones fullpage template. If you need any figures, I find that the quickest way to do this is to just draw a picture by hand and take a photo. You may work with a partner, but writeups must be your own, and both partners must cite one another in their writeups. 1. Why doesn't the metric TSP 2-approximation algorithm work for non-metric TSP? Give an example where it fails. 2. A problem instance--or more precisely, an infinite family of problem instances--is tight for a c-approximation algorithm if the algorithm, when run on these instances, produces solutions with approximation factor c, or approximation factors approaching c in the limit. (Typically when you produce a bad instance, it's clear how to generalize it to a family of instances, varying some parameter, varying edge weights, etc.) Find tight problem instances for: a. the MST-based 2-approximation for metric TSP b. Christofides' algorithm c. the k-center greedy algorithm d. the min makespan 2-approximation e. the min makespan 4/3-approximation 3. Consider a variation of the knapsack FPTAS where v'_i is set to ceil(v_i/mu) rather than to floor(v_i/mu). Prove that this is also gives a (1-eps)-approximation. 4. The first fit algorithm for the bin packing problem simply takes items one at a time, in arbitrary order, and places them in the first bin where they fit. Prove that the number of bins used is at most 2*OPT+1. Next class we'll start (hopefully!) on LP and duality. Here are some warmup exercises: 5. a. V exercise 12.1. b. V exercise 12.2. c. V exercise 12.3.