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

Definition

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

Let be an an instance of 0-1-knapsack, and choose

Create a new rescaled instance with

For a rescaled instance , return the value

of an rescaled optimal solution . Note that uses the original value rather than , i.e., is the original value of the rescaled optimal solution .

Rescaled-DP Algorithm

Rescaled-DP

Let be the knapsack capacity and let

For each and each , define

where if no such subset exists. Thus, is the smallest total size of a subset of the first items whose rescaled value is exactly .

Initialise the table by

For , compute

The maximum feasible rescaled value is

Backtracking through the table recovers a corresponding rescaled optimal solution . Return its original value

The table has entries, each computed in constant time. Hence, Rescaled-DP runs in

time.

Approximation Scheme

Approximation Scheme

The value found by the Rescale-DP algorithm is at least for some .

Approximation Scheme

Let be an optimal solution for an instance . We want to investigate the loss between the optimum and value , i.e.,

We already know that is the value of the solution and we already defined , hence

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 , for the reals, thus

Further, we know that

We conclude that the following chain holds:

Amazing. Next, rewrite the middle part as

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

for some .

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

for some .

Therefore, the loss has an upper bound

Consider the two new sums. We know that is optimal w.r.t. , i.e.,

Therefore

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

We can go further. We know that the optimum is at least the maximum value , i.e.,

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

Rearrange:

FPTAS

The algorithm is an FPTAS for Max-Value Knapsack.

For every , the value-scaling Rescale-DP algorithm returns a feasible solution with original value

and runs in 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 and .

Approximation guarantee. By the previous lemma, the returned solution has original value

Thus, the algorithm is a -approximation for every .

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

the sum of all rescaled values. We first bound each rescaled value. Since and ,

There are items, so summing this bound gives

As shown in the algorithm section, the dynamic programme has entries and computes each entry in constant time. Substituting the bound above yields

Computing the rescaled values and recovering the selected items each take additional time, which does not change this bound. Therefore, the algorithm has the required approximation guarantee and runs in time polynomial in and . Hence, it is an FPTAS.