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 xi in X has a (positive) weight, denoted by weight(xi). 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 S1, S2 of X, each of weight at most W, whose total weight is maximal.
  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 S1, S2 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