Upper bound for 0-1 knapsack using fractional knapsack

Question

In the traditional fractional version of this problem we take the greedy approach:

1. Order by profit to weight ratio in descending order.
2. Take as much as we can from each item, and when we reach an item $k$ that exceed the weight limit we only take fractional part (let's call it critical item).

Let $S = \{s_1, s_2 \dots s_n\}$ be how much we have taken from the item $i$ and $n$ is the number of items. So it's easy to see that:

• $s_i = 1$ if $i < k$
• $s_i \in [0 \dots 1]$ if $i = k$
• $s_i = 0$ if $i > k$

The greedy strategy doesn't work for the 0-1 version but we can bound the profit from 0-1 version using fractional version.

Let $P_b$ be the real profit returned by 0-1 version and $P_a = max(p_k, \sum_{i=1}^{k-1}{p_i})$, where $p_i$ is the profit from item $i$ (they are ordered by profit to weight ratio like in the fractional version) and $k$ is the critical item.

Show: $P_b \leq 2P_a \leq 2P_b$

---

My attempt:

1. Let's show that $P_a \leq P_b$ (second inequality): In this case $P_b$ is is always grater or equal to $P_a$ because the greedy approach of choosing the $k-1$ items (ordered by profit to weight ratio) doesn't guarantee that the full use of the weight limit and only when we may add item $k$ (if doesn't exceed the weight limit) we may use the full limit, but yet this is not guarantee to be the optimal solution. And the same thing is valid if we choose the item $k$, this one doesn't guarantee the the full use of weight limit so it may not be the optimal solution. Also given that $P_b$ is the optimal solution any other solution will always be less or equal to it.
2. Let's show that $P_b \leq 2P_a$ (first inequality): ?

Answer 1

Ok so with your notation, $P_a$ is essentially the profit returned by the Greedy algorithm while $P_b$ is the optimal value. Let me introduce $P_f$ as the optimal value of the corresponding fractional version of the problem.

Since the fractional version is a relaxation of the 0-1 version, you trivially have $P_b\leq P_f$. Moreover since the fractional part will for sure take the $k-1$ first items but only a fraction of the $k$th one, you have $P_f\leq \sum_{i=1}^{k-1}p_i + p_k \leq 2\cdot\max(\sum_{i=1}^{k-1}p_i, p_k)=2P_a$.

Combining everything, you get $P_b\leq 2P_a$ as desired.