Knapsack Greedy Approximation: Worst Case

Question

I am currently studying approximation algorithms and I have run into an issue with a study problem.

The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, where it sorts by the value/weight ratio, and picks the first item in this list that pushes the weight over the limit, and then picks either all the previous items or this particular item, whichever has a greater value.

The claim is that there is at least one case where this algorithm provides a value half that of the optimal value, but after many fruitless attempts I don't see a way to do this.

I have tried many value/weight pairs of 1/1 with a last pair of 5/6, resulting in a ratio of 5/9. Close, but even if I continue this process I am only going to approach a ratio of 1/2, but never achieve it.

Any hints as to how to proceed?

Answer 1

The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been picked had it fit. Let $\alpha$ be the fraction of $p_k$ that does fit – so $\alpha < 1$. These lecture notes (Claim 2) show that $$ p_1 + \cdots + p_{k-1} + \alpha p_k \geq OPT, $$ where $OPT$ is the optimal solution. In particular, $$ p_1 + \cdots + p_{k-1} + p_k > OPT. $$ The algorithm picks either items $1,\ldots,k-1$ or only item $k$, and there is some choice that results in strictly more than $OPT/2$.

Answer 2

Let's say the knapsack capacity is $2w$. For some small $e>0$, let's say we have three items:

• value $w+4e$, weight $w+2e$
• value $w+2e$, weight $w+e$
• value $w-e$, weight $w-e$

The greedy algorithm has value $w+4e$. But, the maximum attainable value is $2 w + e$. When $e\to 0$, the approximation ratio approaches 2.