Homework 6

1. Vertex Cover is NP-complete, so there is no polynomial-time algorithm that solves Vertex Cover optimally unless P=NP. Prove that this implies that there is no FPTAS for Vertex Cover unless P=NP.
2. Let X be a set of n objects. Each object x_i in X has a (positive) weight, denoted by weight(x_i). Assume all the weights are integers. Furthermore there are two containers that each can carry items of total weight at most W. The goal is to fill the containers with items from X such that the total weight of the items put into the containers is maximized. In other words, we want to find two disjoint subsets S₁, S₂ of X, each of weight at most W, whose total weight is maximal.
   • Give a dynamic-programming algorithm running in O(nW²) time to compute OPT, the value of an optimal solution. Explicitly state and explain the recursive formula on which your algorithm is based.
   • Modify the algorithm so that it reports the elements of an optimal solution, not just the total weight OPT.
3. Consider the same problem as in the previous exercise, but this time without the restriction that all weights are integers. Give an FPTAS for this problem. Prove that your algorithm reports a feasible solution, that is, two disjoint subsets S₁, S₂ of X, each of weight at most W and whose total weight is at least (1-ε) OPT. Also analyze the running time of your algorithm.

   Hint: Use the solution to the previous exercise!