Approximation Algorithms Spring 2014 MP Johnson Homework 1 Due: 6am, Monday 2/17/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. V exercise 1.4. 2. Verify WS Fact 1.10. 3. Here's a bunch of problems that are set cover in disguise. (Recall that H_n = O(ln n).) a. WS exercise 1.6.a. b. Show the same hardness for dominating set. c. Show that dominating set admits a H_n approximation algorithm. What can you improve the subscript to? d. WS exercise 1.4. 4. V exercise 2.9. 5. WS exercise 1.1. (Read part a very carefully.) 6. WS exercise 1.3. 7.a. WS exercise 2.10. b. WS exercise 2.11.b. 8. WS exercise 2.2. 9. WS exercise 2.3. 10. WS exercise 2.4. 11. WS exercise 2.1. (See section 2.2.) 12. WS exercise 2.5. 13. V exercise 3.1. 14.a. Show that the three natural greedy algorithms for knapsack (sort by decreasing value, increasing weight, and decreasing value/weight) can all do arbitrarily badly. b. WS exercise 3.1. Next class, we'll be doing dynamic programming and data rounding (WS ch 3), some of it fairly sophisticated. Here's a warm-up exercise on this topic: 15. The usual knapsack DP fills in a nV x n table, where columns correspond to different possible total values in the knapsack and the rows correspond to different prefixes of available items. (See V ch 8; WS ch 3 presents a somewhat algorithm.) This is a pseudo-polynomial time algorithm. By rounding the values to some precision, an FPTAS is obtained. a. Give the rule for filling in the table in the usual DP. b. Given an alternative (pseudo-polynomial time) knapsack DP where the columns correspond to different possible total weights in the knapsack. c. By rounding the weights, could this alternative DP lead to an FPTAS? Explain.