Max-Value Knapsack Problem

computation

Definition

Max-Value Knapsack Problem

The max-value knapsack problem is a maximisation problem:

Given items $a_1,a_2,\dots ,a_n$, where each $a_i$ has a positive integer value $\mathrm{val}(a_i)\in {\mathbb{Z}}^{+}$ and size $\mathrm{s}(a_i)\in {\mathbb{Z}}^{+}$, and a knapsack size $S$, find a subset of items whose size is bounded by $S$ and total value maximised.

Approaches

For a subset $A$ of items, write

$$\mathrm{val}(A)=\sum _{a\in A}\mathrm{val}(a)\text{and}\mathrm{s}(A)=\sum _{a\in A}\mathrm{s}(a).$$

Greedy Highest Value per Size First

Greedy Highest Value per Size First

Repeatedly add a remaining item with maximum value-to-size ratio

$$\frac{\mathrm{val}(a_i)}{\mathrm{s}(a_i)}$$

as long as the size bound $S$ is not exceeded.

Greedy by value-to-size ratio is not optimal

Let the knapsack size be $S=11$. Consider the following items.

item $a_i$	value $\mathrm{val}(a_i)$	size $\mathrm{s}(a_i)$	ratio $\frac{\mathrm{val}(a_i)}{\mathrm{s}(a_i)}$
$a_1$	$1$	$1$	$1$
$a_2$	$6$	$2$	$3$
$a_3$	$18$	$5$	$\frac{18}{5}$
$a_4$	$22$	$6$	$\frac{11}{3}$
$a_5$	$28$	$7$	$4$

Sorting by ratio yields

$$a_5,a_4,a_3,a_2,a_1.$$

The greedy construction is then:

• choose $a_5$, so the used size is $7$ and the value is $28$;
• $a_4$ does not fit, since $7+6>11$;
• $a_3$ does not fit, since $7+5>11$;
• choose $a_2$, so the used size is $9$ and the value is $34$;
• choose $a_1$, so the used size is $10$ and the value is $35$.

Hence greedy returns

$$\{a_5,a_2,a_1\}$$

with value $35$.

But

$$\{a_3,a_4\}$$

is feasible because $5+6=11$, and it has value $40$.

Therefore this greedy strategy is not always an optimal solution for the max-value knapsack problem.

Best-of-Two Approach

Best-of-Two Approach

Sort the items by decreasing ratio $\frac{\mathrm{val}(a_i)}{\mathrm{s}(a_i)}$. Let $k$ be the smallest index with

$$\sum _{i=1}^{k-1}\mathrm{s}(a_i)\le S\text{and}\sum _{i=1}^k\mathrm{s}(a_i)>S.$$

Define

$$A_1=\{a_1,\dots ,a_{k-1}\},A_2=\{a_k\}.$$

Return the more valuable of $A_1$ and $A_2$.

[!intuition] Visual idea

After sorting by ratio, $A_1$ contains the longest prefix that still fits, while $A_2$ is the first single item that would make the prefix overflow.

Approximation guarantee

The best-of-two approach is a factor-$\frac{1}{2}$ approximation algorithm.

$A_1$ and at most a fraction of $a_k$. Hence its value is at most

$$\mathrm{val}(A_1)+\mathrm{val}(A_2).$$

Every integral solution is also feasible for the fractional relaxation, so

$$\mathrm{OPT}(I)\le \mathrm{val}(A_1)+\mathrm{val}(A_2).$$

Therefore at least one of $A_1$ and $A_2$ has value at least $\frac{1}{2}\mathrm{OPT}(I)$, and returning the better of the two gives the claimed approximation ratio.

Polynomial-time Approximation Scheme

ModGreedyKnapsack

Fix $\epsilon >0$ and let

$$k=\lceil \frac{1}{\epsilon }\rceil -1.$$

Enumerate every subset $A_1$ of at most $k$ items.

For each feasible choice of $A_1$, greedily fill the remaining capacity with items from $A-A_1$ in decreasing order of value-to-size ratio. Let $A_2$ be the set of greedily added items.

Return the set

$$A^{\prime }=A_1\cup A_2$$

of maximum value over all branches.

[!intuition] Visual idea

The PTAS first guesses a small set $A_1$ of at most $k$ items, then fills the remaining capacity greedily with a set $A_2$.

PTAS guarantee

ModGreedyKnapsack is a PTAS for the max-value knapsack problem.

$O^{\ast }$ be an optimal solution. If $|O^{\ast }|\le k$, then one branch guesses $A_1=O^{\ast }$, so the algorithm returns an optimal solution.

Now assume $|O^{\ast }|>k$. Consider the branch in which $A_1$ is chosen as the $k$ most valuable items of $O^{\ast }$. Let the remaining items of $O^{\ast }-A_1$ be ordered by decreasing ratio, and let $a_m$ be the first of them that the greedy completion does not take.

Let $B=A^{\prime }-O^{\ast }$ be the items added by greedy that are not in $O^{\ast }$. The items of $O^{\ast }$ missing from $A^{\prime }$ all have ratio at most $\frac{\mathrm{val}(a_m)}{\mathrm{s}(a_m)}$, while the items in $B$ have ratio at least this large. Moreover, when $a_m$ is first rejected, the remaining capacity is smaller than $\mathrm{s}(a_m)$. Hence

$$\mathrm{val}(O^{\ast })-\mathrm{val}(A^{\prime })<\mathrm{val}(a_m).$$

Since $A_1$ contains the $k$ most valuable items of $O^{\ast }$, the solution $O^{\ast }$ contains at least $k+1$ items of value at least $\mathrm{val}(a_m)$. Therefore

$$\mathrm{val}(O^{\ast })>(k+1)\mathrm{val}(a_m),$$

so

$$\mathrm{val}(a_m)<\frac{\mathrm{val}(O^{\ast })}{k+1}.$$

Combining both inequalities gives

$$\mathrm{val}(A^{\prime })>\left(1-\frac{1}{k+1}\right)\mathrm{val}(O^{\ast }).$$

Because $k+1\ge \frac{1}{\epsilon }$, we obtain

$$\mathrm{val}(A^{\prime })\ge (1-\epsilon )\mathrm{OPT}(I).$$

The algorithm checks $O(n^k)$ branches, and each branch performs only polynomial work. For fixed $\epsilon$, this is polynomial in the input size. Hence the algorithm is a PTAS.

Better schemes

The exponent still depends on $\frac{1}{\epsilon }$. By scaling values and using dynamic programming, one can obtain a fully polynomial-time approximation scheme.