Proving that a greedy algorithm is an $\frac{1}{2}$-Approximation algorithm for the unbounded Knapsack problem

Question

With the unbounded Knapsack problem we have $n$ objects $x_i$, with a value $v_i$ and weight $g_i$ for $i = 1,...,n$, as well as the total capacity of the knapsack $G$. We want to maximize the value packed in the knapsack, where an object $x_i$ can be chosen multiple times. You may assume $g_i \leq G$. Prove the following algorithm is an $\frac{1}{2}$-Approximation algorithm for the unbounded Knapsack problem, meaning $GREEDY(x) \geq \frac{1}{2}OPT(x)$ for all instances $x$ of the problem:

1. Sort the $n$ objects in descending order $\frac{v_i}{g_i}$.
2. Go through the objects from $i = 1,...,n$ and pack as many duplicates of the object $x_i$ as long as there is still space left for this object, before moving on to the next one.

I'm really struggling with these proofs for approximation algorithms, since I just can't quite develop an intuition for them, so I'm wondering if someone could help me here.

Answer 1

Here is a sketch of the proof. For the intuition on how you can get this algorithm, it is very similar to the normal knapsack LP argument to show that the greedy algorithm is a $2-$approximation.

We will begin by writing a Linear Program relaxation for the problem. We let $x_j$ denote how many of item $j$ we choose (after the sort).

\begin{array}{ll} \text{maximize} & \sum_{j}v_jx_j \\ \text{subject to}& \sum_{j}x_jg_j \leq G \\ &0 \le x_j \end{array}

Now prove that the solution $(\frac{G}{g_1}, 0,...,0)$, maximizes the LP. Hint: Use a replacement argument + The sorted order of the items.

Now if you think about the greedy algorithm you described, it generates the following solution using the algorithm

$$x_1 = \lfloor \frac{G}{g_1} \rfloor \quad rem_1=G-x_1g_1$$ $$x_2 = \lfloor \frac{r_1}{g_2} \rfloor \quad rem_2=rem_1-x_2g_2$$ $$...$$ $$x_i = 0 \quad \forall i\geq k$$

Finally, if you let $F({\bf x})$ denote the value of the LP for solution ${\bf x}$, then we have that

$$OPT(x) \leq F(\frac{G}{g_1}, 0, ..., 0) = F(\lfloor \frac{G}{g_1} \rfloor,0,...,0) + F(\alpha,0,...,0) \leq F(x_1, x_2, ..., x_n) + F(\alpha, 0, ..., 0) = (*)$$

Where $\alpha = \frac{G}{g_1} - \lfloor \frac{G}{g_1} \rfloor < 1$

Since $F(x_1, x_2, ..., x_n)=Greedy(x)$ and the greedy algorithm choose at least one of the first item (using the assumption $g_1\leq G$), then we have that $$ (*) \leq GREEDY(x) + GREEDY(x) = 2GREEDY(x)$$