Approximation Algorithm (4): Knapsack

Problem is like below. There is a set of items $I = \{1,2,\cdots,n$}, where each item $i$ has a value $v_i \gt 0$ and a size $s_i \gt 0$. Now, knapsack problem is a “Find the maximum possible value with capacity $B$”.

There is a well-known dynamic programming algorithm to solve this.

$\operatorname{for} j \leftarrow 0, \cdots, B$

$\operatorname{OPT}_{0, j} \leftarrow 0$

$\operatorname{for} i \leftarrow 1, \cdots, n$

$\operatorname{for} j \leftarrow 0, \cdots, B$

$\operatorname{if} w_i > j$

$\operatorname{OPT}_{i, j} \leftarrow \operatorname{OPT}_{i - 1, j}$

$\operatorname{else}$

$\operatorname{OPT}_{i, j} \leftarrow \max(\operatorname{OPT}_{i -1, j}, \operatorname{OPT}_{i - 1, j - w_i} + v_i)$

$\operatorname{return} OPT_{n, B}$

In this case, $\operatorname{OPT}_{i,j}$ means an optimal value possible with $1,2,\cdots, i$ items and capacity below $j$.

There is an alternative algorithm to solve this.

$V \leftarrow \sum\limits_{i = 1}^{n} v_i$
$\operatorname{for} j \leftarrow 0, \cdots, V$

$\operatorname{OPT}_{0, j} \leftarrow \infty$

$\operatorname{for} i \leftarrow 1, \cdots, n$

$\operatorname{for} j \leftarrow 0, \cdots, V$

$\operatorname{if} j < v_i$

$\operatorname{OPT}_{i, j} \leftarrow \operatorname{OPT}_{i - 1, j}$

$\operatorname{else}$

$\operatorname{OPT}_{i, j} \leftarrow \max(\operatorname{OPT}_{i -1, j}, \operatorname{OPT}_{i - 1, j - v_i} + s_i)$

$\operatorname{return}(\max_{j=1}^{W}{j | OPT_{n, j} \le B})$

In this case, $\operatorname{OPT}_{i,j}$ means the smallest size possible with $1,2,\cdots, i$ items with value below $j$. We thus have two options: an algorithm bounded by $O(nB)$ or $O(nV)$.

However, $B$ and $V$ may be arbitrarily large, causing the running time to be too long. We address this by quantizing (scaling and rounding) the values.

Quantization

$M \leftarrow \max_{i \in I} v_i$
$\mu \leftarrow \epsilon \frac{M}{n}$
$\operatorname{for} i \leftarrow 1, \cdots, n$

$v_i \leftarrow$ [$\frac{v_i}{\mu}$]

$V \leftarrow \sum\limits_{i = 1}^{n} v_i$
$\operatorname{for} j \leftarrow 0, \cdots, V$

$\operatorname{OPT}_{0, j} \leftarrow \infty$

$\operatorname{for} i \leftarrow 1, \cdots, n$

$\operatorname{for} j \leftarrow 0, \cdots, V$

$\operatorname{if} j < v_i$

$\operatorname{OPT}_{i, j} \leftarrow \operatorname{OPT}_{i - 1, j}$

$\operatorname{else}$

$\operatorname{OPT}_{i, j} \leftarrow \max(\operatorname{OPT}_{i -1, j}, \operatorname{OPT}_{i - 1, j - v_i} + s_i)$

$\operatorname{return}(\max_{j=1}^{W}{j | OPT_{n, j} \le B})$

From the algorithm above, we can see that an approximation algorithm runs in polynomial time. Let’s define $v_i’$ $=$ [$\frac{v_i}{\mu}$]. Then for the new $V$ value, $V’$ $=$ $\sum\limits_{i = 1}^n v_i’$ $\le$ $\sum\limits_{i = 1}^n (\frac{v_i}{\mu})$ $=$ $\sum\limits_{i = 1}^n (\frac{v_i n}{M \epsilon})$ $\le$ $\sum\limits_{i = 1}^n (\frac{n}{\epsilon})$ $=$ $O(n^2/\epsilon)$.

Now, we need to show that it returns at least $(1 - \epsilon) \cdot \operatorname{OPT}$ to establish it as an FPTAS. To prove this, we need some facts, 1, $M \le OPT$, 2. $\mu v_i’ \le v_i \le \mu(v_i’ + 1)$. Also, we can get $\mu v_i’ \ge v_i - \mu$, $\epsilon M = n \mu$.

Now, let $S$ as a set of items which an algorithm above gives and $O$ as a set of items in an optimal solution. Then, $\sum\limits_{i \in S} v_i$ $\ge$ $\sum\limits_{i \in S} \mu v_i’$ $\ge$ $\sum\limits_{i \in O} \mu v_i’$ $\ge$ $\sum\limits_{i \in O} (v_i - \mu)$ $=$ $\sum\limits_{i \in O}v_i - |O|\mu$ $\ge$ $\sum\limits_{i \in O}v_i - n\mu$ $=$ $\sum\limits_{i \in O}v_i - \epsilon M$ $=$ $\operatorname{OPT} - \epsilon M$ $\ge$ $\operatorname{OPT} - \epsilon \operatorname{OPT}$ $=$ $(1 - \epsilon)\operatorname{OPT}$.