1 of 15

Approximation Algorithms for Knapsack Problems�

1

Tsvi Kopelowitz

Modified by Ariel Rosenfeld

2 of 15

Knapsack

Given: a set S of n objects with weights and values, and a weight bound:

w₁, w₂, …, w_n, B (weights, weight bound).
v₁, v₂, …, v_n (values - profit).�

Find: subset of S with total weight at most B, and maximum total value.

�Formally:

Problem is known to be NP-hard

2

3 of 15

Assumptions

. (every item can be added to T)�
. (non-negative values)�
Values, weights, and bound are all integers.

Note:

This is a maximum problem.
Define: OPT = The optimal solution.�
We will see a 2-approximation for two versions of knapsack.

3

4 of 15

Uniform Knapsack (simple form)

(value=weight)

2-approximation algorithm:

Sort the items such that v₁≥ v₂≥ … ≥ v_n.�
Pick such that and � .

4

5 of 15

Uniform Knapsack (proof)

Claim: .

Proof:

Assume (by contradiction): .�
By the algorithm: => . �
=> =>contradiction. � (Since items were sorted)

5

6 of 15

2-approximation �(general knapsack)

Define ratio: _�
Sort items such that r₁≥ r₂≥ … ≥ r_n.

Pick such that and � .�

If( ) return
else return A.

6

7 of 15

2-approximation try it yourself…

7

8 of 15

2-approximation �(general knapsack)

Claim:

Proof sketch (fill the details yourselves):

Consider fractional knapsack (where we can take some of each item)– the optimal solution is A’= (A and a fraction of v_j+1.)

.�
.�
�

8

9 of 15

9

A(i,j) = Smallest weight subset of objects 1,…,i with a total value of j.

A DP algorithm for knapsack

A 1 2 3 j n v_max

1

2

3

i

n

Upper bound on optimal profit

10 of 15

A DP algorithm for knapsack

�

The result is: max j such that A(n, j) ≤ B.
The runtime is: O(n²v_max)
Pseudo-polynomial

10

11 of 15

Definitions

11

Definition: Fully Polynomial Time Approximation Scheme � (FPTAS)

Given ε, delivers a solution with a ratio of (1- ε) for maximum and a ratio of (1+ ε) for minimum, and runs in time polynomial in the size of the input and (1/ε)

Definition: Pseudo-polynomial

If input of integers is given in unary form, runs in polynomial time.

12 of 15

FPTAS for knapsack

The Idea – use scaling!!

Given error bound , define .�
For each object i, define .

Use DP to find optimal solution OPT’ for the rounded values.
Return the set OPT’ with the original values.

12

13 of 15

Correctness

Claim: �

Proof: For every i: .�

(1) => (3)

(2) (4)

13

14 of 15

Correctness

Proof continued:

(1) (3) ��

(2) (4)

•

14

15 of 15

Complexity and Notes

Time:

algorithm is a FPTAS.

15