Recall that in the Knapsack Problem, one is given a set of items numbered 1, 2, . . . , n, such that the i-th item has value v_i ≥ 0 and size s_i ≥ 0. Given a total size budget B, the problem is to choose a subset S ⊆ {1, 2, . . . , n} so as to maximize the combined value of v_i's, subject to the size constraint that the sum of all s_i ≤ B.
1.a. Consider the following greedy algorithm, GA.
1. Eliminate items whose weight wi is greater than W.
2. For each remaining i, compute the value density ρ_i = v_i/w_i.
3. Sort the remaining items in order of decreasing ρ_i.
4. Choose the longest initial segment of this sorted list that does not violate the size constraint.
Also consider the following even more greedy algorithm, EMGA.
1. Eliminate items whose weight w_i is greater than W.
2. Sort the remaining items in order of decreasing v_i.
3. Choose the longest initial segment of this sorted list that does not violate the size constraint.
For each of these two algorithms, give a counterexample to demonstrate that its approximation ratio is not bounded above by any constant C. (Use di?erent counterexamples for the two algorithms.)
1.b. Now consider the following algorithm: run GA and EMGA, look at the two solutions they produce, and pick the one with higher total value. Prove that this is a 2-approximation algorithm for the Knapsack Problem, i.e. it selects a set whose value is at least half of the value of the optimal set.