- 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.
- 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_{1}, S_{2}of X, each of weight at most W, whose total weight is maximal.- Give a dynamic-programming algorithm running
in O(nW
^{2}) 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.

- Give a dynamic-programming algorithm running
in O(nW
- 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
_{1}, S_{2}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!

Otfried Cheong