Value-scaling FPTAS for Max-value 0-1-Knapsack

Definition

Value-scaling FPTAS for Max-value 0-1-Knapsack

Let $I=(\{v(a_1),\dots ,v(a_n)\},\{s(a_1),\dots ,s(a_n)\})$ be an an instance of 0-1-knapsack, and choose

$$K:=\frac{\epsilon \cdot v_{\max }}{n},\text{where}{v}_{\max }:=\underset{i}{\max }\{v(a_i)\},\epsilon \in (0,1).$$

Create a new rescaled instance $\hat{I}=(\{\hat{v}(b_1),\dots ,\hat{v}(b_n)\},\{\hat{s}(b_1),\dots ,\hat{s}(b_n)\})$ with

$$\hat{v}(b_i):=\lfloor \frac{v(a_i)}{K}\rfloor ,\hat{s}(b_i)=s(a_i).$$

For a rescaled instance $\hat{I}$, return the value

$$\hat{V}=\sum _{b_j\in \hat{S}}v(a_j)$$

of an rescaled optimal solution $\hat{S}$. Note that $\hat{V}$ uses the original value $v(a_j)$ rather than $\hat{v}(b_j)$, i.e., $\hat{V}$ is the original value of the rescaled optimal solution $\hat{S}$.

Rescaled-DP Algorithm

Rescaled-DP

Let $C$ be the knapsack capacity and let

$${\hat{V}}_{\mathrm{sum}}:=\sum _{i=1}^n\hat{v}(b_i).$$

For each $i\in \{0,\dots ,n\}$ and each $q\in \{0,\dots ,{\hat{V}}_{\mathrm{sum}}\}$, define

$$X(i,q):=\min \left\{\sum _{b_j\in T}\hat{s}(b_j)|T\subseteq \{b_1,\dots ,b_i\},\sum _{b_j\in T}\hat{v}(b_j)=q\right\},$$

where $X(i,q):=\infty$ if no such subset exists. Thus, $X(i,q)$ is the smallest total size of a subset of the first $i$ items whose rescaled value is exactly $q$.

Initialise the table by

$$X(0,0):=0,X(0,q):=\infty \text{for every }q>0.$$

For $i\in \{1,\dots ,n\}$, compute

$$X(i,q):=\{\begin{array}{ll}\min \left\{X(i-1,q),\hat{s}(b_i)+X(i-1,q-\hat{v}(b_i))\right\},& \hat{v}(b_i)\le q,\\ X(i-1,q),& \hat{v}(b_i)>q.\end{array}$$

The maximum feasible rescaled value is

$$q^{\ast }:=\max \left\{q\in \{0,\dots ,{\hat{V}}_{\mathrm{sum}}\}\mid X(n,q)\le C\right\}.$$

Backtracking through the table recovers a corresponding rescaled optimal solution $\hat{S}$. Return its original value

$$\hat{V}=\sum _{b_j\in \hat{S}}v(a_j).$$

The table has $(n+1)({\hat{V}}_{\mathrm{sum}}+1)$ entries, each computed in constant time. Hence, Rescaled-DP runs in

$$O(n\cdot {\hat{V}}_{\mathrm{sum}})$$

time.

Approximation Scheme

Approximation Scheme

The value $\hat{V}$ found by the Rescale-DP algorithm is at least $(1-\epsilon )\cdot \mathrm{OPT}(I)$ for some $\epsilon \in (0,1)$.

Approximation Scheme

Let $S$ be an optimal solution for an instance $I$. We want to investigate the loss between the optimum and value $\hat{V}$, i.e.,

$$\mathrm{OPT}(I)-\hat{V}=\dots .$$

We already know that $\mathrm{OPT}(I)$ is the value of the solution $S$ and we already defined $\hat{V}$, hence

$$\mathrm{OPT}(I)-\hat{V}=\sum _{a_i\in S}v(a_i)-\sum _{b_j\in \hat{S}}v(a_j).$$

We want to find an upper bound for that loss, i.e., we want to find an upper bound for the first sum and a lower bound for the second sum.

We already know that $\lfloor x\rfloor \le x\le x+1$, for the reals, thus

$$\hat{v}(b_i)=\lfloor \frac{v(a_i)}{K}\rfloor \le \frac{v(a_i)}{K}\le \frac{v(a_i)}{K}+1.$$

Further, we know that

$$\hat{v}(b_i)+1=\lfloor \frac{v(a_i)}{K}\rfloor +1\le \frac{v(a_i)}{K}+1.$$

We conclude that the following chain holds:

$$\hat{v}(b_i)=\lfloor \frac{v(a_i)}{K}\rfloor \le \frac{v(a_i)}{K}\le \hat{v}(b_i)+1\le \frac{v(a_i)}{K}+1.$$

Amazing. Next, rewrite the middle part as

$$\frac{v(a_i)}{K}\le \hat{v}(b_i)+1⟹v(a_i)\le K\cdot [\hat{v}(b_i)+1].$$

We found an upper bound for the first sum, i.e.,

$$v(a_i)\le K\cdot [\hat{v}(b_i)+1]⟹\sum _{a_i\in X}v(a_i)\le K\cdot \sum _{a_i\in X}\left[\hat{v}(b_i)+1\right]$$

for some $X$.

Further, we already found a lower bound for the second sum, i.e.,

$$\begin{array}{rl}\hat{v}(b_i)=\lfloor \frac{v(a_i)}{K}\rfloor \le \frac{v(a_i)}{K}& ⟹K\cdot \hat{v}(b_i)\le v(a_i)\\ & ⟹K\cdot \sum _{b_i\in X}\hat{v}(b_i)\le \sum _{b_i\in X}v(a_i)\end{array}$$

for some $X$.

Therefore, the loss has an upper bound

$$\begin{array}{rl}\mathrm{OPT}(I)-\hat{V}& \le K\cdot \sum _{a_i\in S}[\hat{v}(b_i)+1]-K\cdot \sum _{b_j\in \hat{S}}\hat{v}(b_j)\\ & =K\cdot \left[\sum _{a_i\in S}[\hat{v}(b_i)+1]-\sum _{b_j\in \hat{S}}\hat{v}(b_j)\right]\\ & =K\cdot \left[|S|+\sum _{a_i\in S}\hat{v}(b_i)-\sum _{b_j\in \hat{S}}\hat{v}(b_j)\right].\end{array}$$

Consider the two new sums. We know that $\hat{S}$ is optimal w.r.t. $\hat{v}$, i.e.,

$$\forall F\in \mathcal{F}(\hat{I}):\sum _{x\in F}\hat{v}(x)\le \sum _{x\in \hat{S}}\hat{v}(x),\mathcal{F}(\hat{I})\text{ is the set of feasible solutions}.$$

Therefore

$$\sum _{a_i\in S}\hat{v}(b_i)\le \sum _{b_j\in \hat{S}}\hat{v}(b_j)⟹\sum _{a_i\in S}\hat{v}(b_i)-\sum _{b_j\in \hat{S}}\hat{v}(b_j)\le 0<1.$$

We found an upper bound for the inner difference. We conclude

$$\begin{array}{rl}\mathrm{OPT}(I)-\hat{V}& \le K\cdot |S|\\ & =\frac{\epsilon \cdot v_{\max }}{n}\cdot |S|.\end{array}$$

We can go further. We know that the optimum $\mathrm{OPT}(I)$ is at least the maximum value $v_{\max }$, i.e.,

$$v_{\max }\le \mathrm{OPT}(I)⟹\mathrm{OPT}(I)-\hat{V}\le \frac{\epsilon \cdot \mathrm{OPT}(I)}{n}\cdot |S|.$$

Further, the optimal and thus feasible $S$ cannot pick more items than $n$. Another upper bound is found:

$$|S|\le n⟹\mathrm{OPT}(I)-\hat{V}\le \frac{\epsilon \cdot \mathrm{OPT}(I)}{\cancel{n}}\cdot \cancel{n}=\epsilon \cdot \mathrm{OPT}(I).$$

Rearrange:

$$\begin{array}{rl}\mathrm{OPT}(I)-\hat{V}\le \epsilon \cdot \mathrm{OPT}(I)& ⟹\mathrm{OPT}(I)-\epsilon \cdot \mathrm{OPT}(I)\le \hat{V}\\ & ⟹(1-\epsilon )\cdot \mathrm{OPT}(I)\le \hat{V}.\end{array}$$

FPTAS

The algorithm is an FPTAS for Max-Value Knapsack.

For every $\epsilon \in (0,1)$, the value-scaling Rescale-DP algorithm returns a feasible solution with original value

$$\hat{V}\ge (1-\epsilon )\cdot \mathrm{OPT}(I)$$

and runs in $O\left(\frac{n^3}{\epsilon }\right)$ time.

The algorithm is an FPTAS for Max-Value Knapsack.

We must show two facts: the algorithm achieves the required approximation guarantee, and its running time is polynomial in both $n$ and $\frac{1}{\epsilon }$.

Approximation guarantee. By the previous lemma, the returned solution $\hat{S}$ has original value

$$\hat{V}\ge (1-\epsilon )\cdot \mathrm{OPT}(I).$$

Thus, the algorithm is a $(1-\epsilon )$-approximation for every $\epsilon \in (0,1)$.

Running time. The running time of Rescaled-DP depends on

$${\hat{V}}_{\mathrm{sum}}:=\sum _{i=1}^n\hat{v}(b_i),$$

the sum of all rescaled values. We first bound each rescaled value. Since $v(a_i)\le v_{\max }$ and $K=\frac{\epsilon v_{\max }}{n}$,

$$\begin{array}{rl}\hat{v}(b_i)& =\lfloor \frac{v(a_i)}{K}\rfloor \\ & \le \frac{v(a_i)}{K}\\ & \le \frac{v_{\max }}{K}\\ & =\frac{v_{\max }}{\epsilon v_{\max }/n}\\ & =\frac{n}{\epsilon }.\end{array}$$

There are $n$ items, so summing this bound gives

$${\hat{V}}_{\mathrm{sum}}=\sum _{i=1}^n\hat{v}(b_i)\le \sum _{i=1}^n\frac{n}{\epsilon }=\frac{n^2}{\epsilon }.$$

As shown in the algorithm section, the dynamic programme has $O(n{\hat{V}}_{\mathrm{sum}})$ entries and computes each entry in constant time. Substituting the bound above yields

$$O\left(n{\hat{V}}_{\mathrm{sum}}\right)\le O\left(n\cdot \frac{n^2}{\epsilon }\right)=O\left(\frac{n^3}{\epsilon }\right).$$

Computing the rescaled values and recovering the selected items each take $O(n)$ additional time, which does not change this bound. Therefore, the algorithm has the required approximation guarantee and runs in time polynomial in $n$ and $\frac{1}{\epsilon }$. Hence, it is an FPTAS.