The ModGreedyKnapsack Algorithm is a PTAS

Let $\Pi$ be the max-value knapsack problem with

• a fixed $k=\lceil \frac{1}{\epsilon }\rceil -1$,
• a finite set of items $A=\{a_1,\dots ,a_n\}$,
• a size function $s$,
• a value function $v$, and
• a knapsack capacity of $S$.

Consider the following algorithm $\mathcal{A}$:

1. Enumerate all $A_1^{\prime }\subseteq A$ of at most size $k$, i.e., enumerate all ${\sum }_{j=0}^k\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ combinations.
2. Discard the branch if $s(A_1^{\prime })>S$. Otherwise, scan the items in $A\setminus A_1^{\prime }$ in descending order of the ratio $\frac{v(a)}{s(a)}$ and add an item whenever it fits, i.e., whenever $s(a)\le S-s(A_1^{\prime })-s(A_2^{\prime })$. The set of those greedily-selected items is denoted by $A_2^{\prime }$.
3. Each branch constructs a (possibly non-optimal) solution $A^{\prime }=A_1^{\prime }\cup A_2^{\prime }$.
4. At the end, choose an $A^{\prime }$ of highest value.

To prove that the described algorithm is a PTAS, we have to show the following two properties:

1. $\forall I\in D_{\Pi }:v(\mathcal{A}(I,\epsilon ))\ge (1-\epsilon )\cdot \text{OPT}(I)$.
2. $\forall I\in D_{\Pi }:T(I,\epsilon )\le |I{|}^{g(\epsilon )}$, with $T$ being the running time.

Approximation guarantee

Let $O^{\ast }$ be an optimal solution for $\Pi$. Consider both cases:

1. $|O^{\ast }|\le k$: The branch $A_1^{\prime }=O^{\ast }$ is enumerated. Its candidate has value at least $v(O^{\ast })$, so the algorithm $\mathcal{A}$ outputs an optimal solution.
2. $|O^{\ast }|>k$: The optimal solution isn’t fully covered by the all-enumeration, which requires special treatment.

Consider the branch in which $A_1^{\prime }$ consists of the $k$ most valuable items of $O^{\ast }$. This branch fills the remaining capacity $S-s(A_1^{\prime })$ greedily with $x$ items

$$\frac{v(a_{k+1})}{s(a_{k+1})}\ge \frac{v(a_{k+2})}{s(a_{k+2})}\ge \cdots \ge \frac{v(a_{k+x})}{s(a_{k+x})},$$

where $a_{k+1},a_{k+2},\dots ,a_{k+x}\in A_2^{\prime }=A^{\prime }\setminus A_1^{\prime }$.

How does $A^{\prime }=A_1^{\prime }\cup A_2^{\prime }$ relate to $O^{\ast }$? If greedy selects every item in $O^{\ast }\setminus A_1^{\prime }$, then $A^{\prime }$ is optimal. Otherwise, let $a$ be the first item of $O^{\ast }\setminus A_1^{\prime }$ that does not fit. Immediately before $a$ is considered, define

$$\begin{array}{rl}O& :=\{o\in O^{\ast }\setminus A_1^{\prime }:o\text{ was already selected}\},\\ M& :=(O^{\ast }\setminus A_1^{\prime })\setminus O,\\ B& :=\{b\in A_2^{\prime }\setminus O^{\ast }:b\text{ was selected before }a\}.\end{array}$$

• Optimal items: Items from $O^{\ast }\setminus A_1^{\prime }$ that were selected before $a$.
• Missed items: Items from $O^{\ast }\setminus A_1^{\prime }$ that were not selected before $a$. In particular, $a\in M$.
• Non-optimal items: Items outside $O^{\ast }$ that were selected before $a$.

The first missed optimal item $a$ marks a cut in the density-ordered scan:

Let $C:=A_1^{\prime }\cup O\cup B$ be the partial candidate immediately before $a$ is considered. Since the final candidate $A^{\prime }$ contains $C$,

$$v(O^{\ast })-v(A^{\prime })\le v(O^{\ast })-v(C)=v(M)-v(B).$$

Consider the missing items first. Since $a$ is the first missed optimal item and the items are processed in descending order of ratio, we have

$$\forall m\in M:\frac{v(m)}{s(m)}\le \frac{v(a)}{s(a)}.$$

Equivalently:

$$\frac{v(m)}{s(m)}\le \frac{v(a)}{s(a)}⟺v(m)\le s(m)\cdot \frac{v(a)}{s(a)}.$$

Therefore, we found an upper bound for the first term already:

$$\begin{array}{rl}v(M)& =\sum _{m\in M}v(m)\\ & \le \sum _{m\in M}s(m)\cdot \frac{v(a)}{s(a)}\\ & =\frac{v(a)}{s(a)}\cdot \sum _{m\in M}s(m)\\ & =\frac{v(a)}{s(a)}\cdot s(M).\end{array}$$

Next, we want to find a lower bound for $v(B)$. Every $b\in B$ was selected before $a$, so $b$‘s ratio must be greater than or equal to $a$‘s ratio, i.e.,

$$\forall b\in B:\frac{v(b)}{s(b)}\ge \frac{v(a)}{s(a)}.$$

Equivalently,

$$\frac{v(b)}{s(b)}\ge \frac{v(a)}{s(a)}⟺v(b)\ge s(b)\cdot \frac{v(a)}{s(a)}.$$

Therefore:

$$\begin{array}{rl}v(B)& =\sum _{b\in B}v(b)\\ & \ge \sum _{b\in B}s(b)\cdot \frac{v(a)}{s(a)}\\ & =\frac{v(a)}{s(a)}\cdot s(B).\end{array}$$

Equivalently:

$$v(B)\ge \frac{v(a)}{s(a)}\cdot s(B)⟺-v(B)\le -\frac{v(a)}{s(a)}\cdot s(B).$$

Putting them together yields

$$\begin{array}{rl}v(O^{\ast })-v(A^{\prime })& \le v(M)-v(B)\\ & \le \frac{v(a)}{s(a)}\cdot s(M)-\frac{v(a)}{s(a)}\cdot s(B)\\ & =\frac{v(a)}{s(a)}\cdot (s(M)-s(B)).\end{array}$$

What’s $s(M)-s(B)$? We know that the optimal solution $O^{\ast }$ consists of the enumerated items, the optimal items selected before $a$, and the missing optimal items, i.e.,

$$O^{\ast }=A_1^{\prime }\dot{\cup }O\dot{\cup }M.$$

Hence, we can infer from the feasibility of $O^{\ast }$ that

$$\begin{array}{rl}s(A_1^{\prime })+s(O)+s(M)& =s(O^{\ast })\\ & \le S.\end{array}$$

Equivalently:

$$s(M)-s(B)\le S-s(A_1^{\prime })-s(O)-s(B).$$

The right-hand side is precisely the free capacity immediately before $a$ is considered. Since $a$ does not fit, we know that

$$S-s(A_1^{\prime })-s(O)-s(B)<s(a).$$

The two knapsacks below compare the same shared prefix $A_1^{\prime }\cup O$. The current greedy prefix spends some capacity on $B$; the optimal solution instead spends capacity on $M$.

Therefore,

$$\begin{array}{rl}v(O^{\ast })-v(A^{\prime })& \le \frac{v(a)}{s(a)}\cdot (s(M)-s(B))\\ & <\frac{v(a)}{s(a)}\cdot s(a)\\ & =v(a).\end{array}$$

It remains to relate $v(a)$ to $v(O^{\ast })$. Since $A_1^{\prime }$ contains the $k$ most valuable items of $O^{\ast }$ and $a\in O^{\ast }\setminus A_1^{\prime }$, every item in $A_1^{\prime }$ has value at least $v(a)$. Hence,

$$\begin{array}{rl}v(O^{\ast })& \ge v(A_1^{\prime })+v(a)\\ & \ge (k+1)v(a).\end{array}$$

Equivalently,

$$v(a)\le \frac{v(O^{\ast })}{k+1}.$$

The reason for the denominator $k+1$ is that $O^{\ast }$ contains $k$ guessed items, each worth at least $v(a)$, together with $a$ itself:

Putting both bounds together yields

$$\begin{array}{rl}v(A^{\prime })& >v(O^{\ast })-v(a)\\ & \ge \left(1-\frac{1}{k+1}\right)v(O^{\ast }).\end{array}$$

By the choice $k=\lceil \frac{1}{\epsilon }\rceil -1$, we have

$$\frac{1}{k+1}\le \epsilon .$$

Consequently,

$$v(A^{\prime })\ge (1-\epsilon )v(O^{\ast })=(1-\epsilon )\mathrm{OPT}(I).$$

Since the algorithm returns the most valuable candidate among all enumerated branches, its output has at least the value of this particular $A^{\prime }$. Therefore,

$$v(\mathcal{A}(I,\epsilon ))\ge (1-\epsilon )\mathrm{OPT}(I),$$

which proves the approximation condition.

Running-time

The density order can be computed once and reused by every branch. Sorting the $n$ items by $\frac{v(a)}{s(a)}$ takes $O(n\log n)$ time. Ratios need not be represented explicitly: two items $a_i$ and $a_j$ can be compared by cross-multiplying

$$v(a_i)s(a_j)\text{and}v(a_j)s(a_i).$$

The number of enumerated subsets is

$$\begin{array}{rl}\sum _{j=0}^k\left(\genfrac{}{}{0ex}{}{n}{j}\right)& \le \sum _{j=0}^k{n}^j\\ & \le (k+1)n^k.\end{array}$$

For each subset $A_1^{\prime }$, the algorithm computes $s(A_1^{\prime })$ and then scans the density-ordered list once, skipping the items in $A_1^{\prime }$ and adding every item that fits. Since $k$ is fixed for a fixed $\epsilon$, this requires $O(n)$ time per branch.

Consequently,

$$\begin{array}{rl}T(n,\epsilon )& =O\left(n\log n+n\sum _{j=0}^k\left(\genfrac{}{}{0ex}{}{n}{j}\right)\right)\\ & =O\left(n\log n+(k+1)n^{k+1}\right).\end{array}$$

For every fixed $0<\epsilon <1$, the value

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

is constant with respect to the input. Moreover,

$$k+1=\lceil \frac{1}{\epsilon }\rceil ,$$

so the running time simplifies to

$$T(n,\epsilon )=O\left(n^{\lceil 1/\epsilon \rceil }\right).$$

Since $n\le |I|$, this is polynomial in $|I|$ for every fixed $\epsilon$. Under the unit-cost model, we may choose

$$g(\epsilon )=\lceil \frac{1}{\epsilon }\rceil$$

and obtain

$$T(I,\epsilon )=O\left(|I{|}^{g(\epsilon )}\right).$$

Arithmetic on binary-encoded sizes and values contributes only another factor $|I{|}^c$ in the bit model, where $c$ is a constant independent of $I$ and $\epsilon$. In that model, choose instead

$$g(\epsilon )=\lceil \frac{1}{\epsilon }\rceil +c.$$

Thus, for every fixed $\epsilon$, the algorithm runs in polynomial time. Together with the approximation guarantee, this proves that $\mathcal{A}$ is a PTAS.