Questions 1 and 2

• In questions 1) and 2a), the value epsilon is in the interval (0,1], i.e. it is a real number. You can assume that it is rational.

• We have so far defined KNAPSACK as having profits and weights that are natural numbers. In answering questions 1) and 2a) you may find it useful to have weights and profits that are rational numbers; note that you can convert an instance with rational numbers to an instance with integers by multiplying each w_i and p_i, and W, by the largest of the denominators. A solution is feasible for the new instance iff it is feasible for the old instance, and the profit of every feasible solution is scaled by exactly the factor by which we multiplied (so in particular the optimal solutions, and the approximation ratio achieved by feasible solutions, are unchanged). Also, the ratio p_i/w_i is unchanged so the algorithm returns the same set of items in both instances.

  In particular, it may be helpful to think of W=1, and choose weights w_i in [0,1].

• I have the impression that question 2b) is more difficult than I intended. You do not have to do this question. If you already have a solution, feel free to submit it: there will be a small bonus for answers that are correct (but no part marks).