Approximation Algorithms
Spring 2014
MP Johnson

Homework 3

Due: problems 1 and 2 before class on March 12; the rest: before class, May 7

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.


0. Any problems from earlier homeworks that you didn't complete (because of time
constraints rather than because of impossibility).


*************************************************************************************

DUE before class, Wednesday, March 12.  PLAIN TEXT email is fine for these.

1. Briefly explain IP formulation (4.9) of WS (page 89 section 4.6) in your own words: 
what the vars mean, what the constraints are doing, why solving that IP solves bin 
packing.


2. Write down IP formulations for the following problems:

a. maximum independent set
b. minimum vertex cover
c. shortest path (from node v_s to node v_t)


*************************************************************************************


STARTING HERE, DUE: ???

2.d. maximum matching (on general weighted graphs)
e. TSP
f. max flow


3. V exercise 13.4. parts 1 and 2. 


4. WS exercise 4.6.a. After reading through the problem and its own hint, what's left 
for you to do is to find a way to repeatedly modify the fractional solution in such a 
way that the solution value gets no worse and you reduce the number of non-integral 
vars (edges). Which maybe isn't itself that simple to do. So...

Further hints (don't read more of them than necessary and spoil your fun!):

1) Let H be the subgraph of G whose edge vars are currently fractional (i.e.,
0 < x_{ij} < 1).

2) Suppose there's a cycle C in H. What are two different ways you could you modify C's 
edge vars in  order to reduce the number of fractional edges by (at least) one? How do 
these two resulting solution values compare to the old solution value (and to each 
other)?

3) OK, suppose there (now) aren't any cycles in H. So take some maximal *path* in H. 
What are two ways you could modify *it*? ...


5. WS exercise 2.11.b. That is, show that an approximation algorithm for max coverage
with factor better than 1-1/e would imply an approximation algorithm for set cover with
factor better than log_e(n).

Hint: Suppose you have a c-approximation max coverage algorithm A, and think about what
you could do with it on a given max coverage / set cover instance I. First, "guess" the 
minimum number of sets k needed cover all elements of I. (That is, hypothetically repeat 
the following strategy for every possible value of k from 1 to # sets.) If you ran A on
(I,k), it would cover at least c*n elements (why?), leaving at most (1-c)*n uncovered.
If you ran A on (I',k), where I' is the instance consisting of the elements left
uncovered the first time, you'll be left with at most (1-c)^2*n uncovered elements.
Suppose that after L iterations you have (1-c)^L*n < 1.

Given the known hardness result, what do you know about L?

Given this, what can you say about c?


9. WS exercise 5.1. 


10. WS exercise 5.2. 


11. V exercise 16.2. 


*************************************************************************************


DUE before class, Wednesday, March 17. Please use Latex as usual.

6. Recall again LP formulation (4.9) from section 4.6 of WS. Consider the following
problem instance I:

s1=.6, s2=.3, s3=.2
b1=2,  b2=1,  b3=3

a. Say that a feasible configuration is maximal if it is not a strict subset of any
other feasible configuration. Write down all the maximal feasible configurations (with
the understanding that feasibility is closed under subset).

Now suppose we're given the dual solution y1=.55, y2=.5, y3=.25, and consider the
following knapsack instance, with capacity 1 and objects of the form (val_i,weight_i) = 
(y_i, s_i):

b1=2 copies of object: (val,weight) = (.55,.6)
b2=1 copy of   object: (val,weight) = (.5,.3)
b3=3 copies of object: (val,weight) = (.25,.2)

(Notice that this instance is constructed slightly differently from the one in class...)

b. When the separation oracle solves this knapsack problem, does it report that the dual
solution (y1,y2,y3) is feasible, or does it return a violated constraint? If so, which
one?

c. Now think about the configuration IP corresponding to our bin packing instance I.
Clearly OPT_IP(I) = 3. What is SIZE(I)?

d. What is OPT_LP(I)? (Hence what can we say about SIZE v. OPT_LP in general?)


7. Rewrite the proof of WS's Lemma 4.16 in your own words, filling in the missing
details, though ignoring the "In fact" at the end. (For example, why precisely can the
pieces of I' be mapped to pieces of I? Why does the second "hence" follow?)


8. WS exercise 7.3a,b,c. (See also Algorithm 2.17, which is given with exercise 2.11 in
V. That algorithm is the same algorithm described in the text of this exercise, except
written in terms of Vertex Cover. Notice that when Vertex Cover is interpreted as a
special case of Set Cover, it has f = 2.)

*************************************************************************************