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.