Approximation Algorithms: Knapsack

This is the lecture notes from Chandra Chekuri's CS583 course on Approximation Algorithms. Chapter 3: Knapsack. You can read Chapter 4: Packing Problems, here. Chapter 2: Covering problems, here.

Chapter 3

In this lecture we explore the Knapsack problem. This problem provides a good basis for learning some important procedures used for approximation algorithms that give better solutions at the cost of higher running time.

3.1 The Knapsack Problem

In the Knapsack problem we are given a number (knapsack capacity)

B \geq 0

, and a set

N

n

items; each item

i

has a given size

s_{i} \geq 0

and a profit

p_{i} \geq 0

. We will assume that all the input numbers are integers (or more generally rationals). Given a subset of the items

A \subseteq N

, we define two functions,

s (A) = \sum_{i \in A} s_{i}

and

p (A) = \sum_{i \in A} p_{i}

, representing the total size and profit of the group of items respectively. The goal is to choose a subset of the items,

A

, such that

s (A) \leq B

and

p (A)

is maximized. We will assume, without loss of generality, that

s_{i} \leq B

for all

i

; we can discard items that do not satisfy this constraint.

It is not difficult to see that if all the profits are identical (say 1), the natural greedy algorithm that inserts items in the order of non-increasing sizes yields. Assuming the profits and sizes are integral, we can still find an optimal solution to the problem using dynamic programming in either

O (n B)

O (n P)

time, where

P = \sum_{i = 1}^{n} p_{i}

. These are standard exercises. While these algorithms appear to run in polynomial time, it should be noted that

B

and

P

can be exponential in the size of the input written in binary. We call such algorithms pseudo-polynomial time algorithms as their running times are polynomial when numbers in the input are given in unary. Knapsack is a classical NP-Hard problem and these results (and the proof of NP-Hardness) show that the hardness manifests itself when the numbers are large (exponential in

n

which means that the number of bits in the size or profit are polynomial in

n

3.1.1 A Greedy Algorithm

Consider the following greedy algorithm for the Knapsack problem which we will refer to as GreedyKnapsack. We sort all the items by the ratio of their profits to their sizes so that

\frac{p_{1}}{s_{1}} \geq \frac{p_{2}}{s_{2}} \geq \dots \geq \frac{p_{n}}{s_{n}}

. Afterward, we greedily take items in this order as long as adding an item to our collection does not exceed the capacity of the knapsack. It turns out that this algorithm can be arbitrarily bad. Suppose we only have two items in

N

. Let

s_{1} = 1, p_{1} = 2

s_{2} = B

, and

p_{2} = B

. GreedyKnapsack will take only item

1

, but taking only item

2

would be a better solution and the ratio of the profits in the two cases is

2 / B

which can be made arbitrarily small. As it turns out, we can easily modify this algorithm to provide a

2

-approximation by simply taking the best of GreedyKnapsack's solution or the most profitable item. We will call this new algorithm ModifiedGreedy.

Theorem 3.1. ModifiedGreedy has an approximation ratio of

1 / 2

for the Knapsack problem.

Proof. Let

k

be the index of the first item that is not accepted by GreedyKnapsack. Consider the following claim:

Claim 3.1.1.

p_{1} + p_{2} + \dots p_{k} \geq OPT

. In fact,

p_{1} + p_{2} + \dots + α p_{k} \geq OPT

where

α = \frac{B - (s_{1} + s_{2} + \dots + s_{k - 1})}{s_{k}}

is the fraction of item

k

that can still fit in the knapsack after packing the first

k - 1

items.

The proof of Theorem 3.1 follows immediately from the claim. In particular, either

p_{1} + p_{2} + \dots + p_{k - 1}

p_{k}

must be at least

OPT / 2

. We now only have to prove Claim 3.1.1. We give an

LP

relaxation of the Knapsack problem as follows: Here,

x_{i} \in [0, 1]

denotes the fraction of item

i

packed in the knapsack.

\begin{aligned} maximize \sum_{i = 1}^{n} p_{i} x_{i} \\ subject to \sum_{i = 1}^{n} s_{i} x_{i} & \leq B \\ x_{i} & \leq 1 for all i in {1 \dots n} \\ x_{i} & \geq 0 for all i in {1 \dots n} \end{aligned}

Let

{OPT}_{L P}

be the optimal value of the objective function in this linear programming instance. Any solution to Knapsack is a feasible solution to the

LP

and both problems share the same objective function, so

{OPT}_{L P} \geq OPT

. Now set

x_{1} = x_{2} = \dots = x_{k - 1} = 1, x_{k} = α

, and

x_{i} = 0

for all

i > k

. This is a feasible solution to the

LP

. We leave it as an exercise to the reader to argue that is an optimum solution. Therefore,

p_{1} + p_{2} + \dots + α p_{k} = {OPT}^{'} \geq OPT

. The first statement of the lemma follows from the second as

α \leq 1

3.1.2 A Polynomial Time Approximation Scheme

Using the results from the last section, we make a few simple observations. Some of these lead to a better approximation.

Observation 3.2. If for all

i, p_{i} \leq ϵ OPT

, GreedyKnapsack gives

a (1 - ϵ)

approximation.

Proof. Follows easily from Claim 3.1.1.

Observation 3.3. There are at most

⌈ \frac{1}{ϵ} ⌉

items with profit at least

ϵ OPT

in any optimal solution.

The next claim is perhaps more interesting and captures the intuition that the bad case for greedy happens only when there are "big" items.

Claim 3.1.2. If for all

i, s_{i} \leq ϵ B

, GreedyKnapsack gives a

(1 - ϵ)

approximation.

Proof. We give a proof sketch via the

LP

relaxation. Recall that

k

is the first item that did not fit in the knapsack. We make the following observation. Recall that

{OPT}_{L P}

is the optimum value of

LP

relaxation. Suppose we reduce the knapsack capacity to

B^{'} = s_{1} + s_{2} + \dots s_{k - 1}

while keeping all the items the same. Let

{OPT}_{L P}^{'}

be the value for the new size. We claim that

{OPT}_{L P}^{'} \geq \frac{B^{'}}{B} {OPT}_{L P}

–this is because we can take any feasible solution to the original

LP

and scale each variable by

B^{'} / B

to obtain a feasible solution with the new capacity. What is

{O P T}_{L P}^{'}

? We note that Greedy will fill

B^{'}

to capacity with the first

k - 1

items and hence,

{OPT}_{L P}^{'} = p_{1} + \dots + p_{k - 1}

. Combining, we obtain that

p_{1} + \dots + p_{k - 1} \geq \frac{B^{'}}{B} {OPT}_{L P} \geq \frac{B^{'}}{B} OPT .

We note that

B^{'} + s_{k} \geq B

since item

k

did not fit, and hence

B^{'} \geq B - s_{k} \geq B - ϵ B \geq

(1 - ϵ) B

. Therefore

B^{'} / B \geq (1 - ϵ)

and this finishes the proof.

We may now describe the following algorithm. Let

ϵ \in (0, 1)

be a fixed constant and let

h = ⌈ \frac{1}{ϵ} ⌉

. We will try to guess the

h

most profitable items in an optimal solution and pack the rest greedily.

\underline{Guess H+ Greedy (N, B)}

For each $S \subseteq N$ such that $| S | \leq h$ and $s (S) \leq B$ do

A.Pack $S$ in knapsack of size at most $B$
B.Let $i$ be the least profitable item in $S$ . Remove all items $j \in N - S$ where $p_{j} > p_{i}$ .
C.Run GreedyKnapsack on remaining items with remaining capacity $B - \sum_{i \in S} s_{i}$

Output best solution from above

Theorem 3.4. Guess

H +

Greedy gives a

(1 - ϵ)

approximation and runs in

O (n^{⌈ 1 / ϵ ⌉ + 1})

time.

Proof. For the running time, observe that there are

O (n^{h})

subsets of

N

. For each subset, we spend linear time greedily packing the remaining items. The time initially spent sorting the items can be ignored thanks to the rest of the running time.

For the approximation ratio, consider a run of the loop where

S

actually is the

h

most profitable items in an optimal solution and the algorithm's greedy stage packs the set of items

A^{'} \subseteq (N - S)

. Let

{OPT}^{'}

be the optimal way to pack the smaller items in

N - S

so that

OPT = p (S) + {OPT}^{'}

. Let item

k

be the first item rejected by the greedy packing of

N - S

. We know

p_{k} \leq ϵ OPT

so by Claim 3.1.1

p (A^{'}) \geq {OPT}^{'} - ϵ OPT

. This means the total profit found in that run of the loop is

p (S) + p (A^{'}) \geq (1 - ϵ) OPT

Note that for any fixed choice of

ϵ > 0

, the preceding algorithm runs in polynomial time. This type of algorithm is known as a polynomial time approximation scheme or

PTAS

. The term "scheme" refers to the fact that the algorithm varies with

ϵ

. We say a maximization problem

Π

has a

PTAS

if for all

ϵ > 0

, there exists a polynomial time algorithm that gives a

(1 - ϵ)

approximation

((1 + ϵ)

for minimization problems). In general, one can often find a

PTAS

for a problem by greedily filling in a solution after first searching for a good basis on which to work. As described below, Knapsack actually has something stronger known as a fully polynomial time approximation scheme or

FPTAS

. A maximization problem

Π

has a

FPTAS

if for all

ϵ > 0

, there exists an algorithm that gives a

(1 - ϵ)

approximation

((1 + ϵ)

for minimization problems) and runs in time polynomial in both the input size and

1 / ϵ

3.1.3 Rounding and Scaling

Earlier we mentioned exact algorithms based on dynamic programming that run in

O (n B)

and

O (n P)

time but noted that

B

and

P

may be prohibitively large. If we could somehow decrease one of those to be polynomial in

n

without losing too much information, we might be able to find an approximation based on one of these algorithms. Let

p_{max} = max_{i} p_{i}

and note the following.

Observation 3.5.

p_{max} \leq OPT \leq n p_{max}

Now, fix some

ϵ \in (0, 1)

. We want to scale the profits and round them to be integers so we may use the

O (n P)

algorithm efficiently while still keeping enough information in the numbers to allow for an accurate approximation. For each

i

, let

p_{i}^{'} = ⌊ \frac{n}{ϵ} \frac{1}{p_{max}} p_{i} ⌋

. Observe that

p_{i}^{'} \leq \frac{n}{ϵ}

so now the sum of the profits

P^{'}

is at most

\frac{n^{2}}{ϵ}

. Also, note that we lost at most

n

profit from the scaled optimal solution during the rounding, but the scaled down

OPT

is still at least

\frac{n}{ϵ}

. We have only lost an

ϵ

fraction of the solution. This process of rounding and scaling values for use in exact algorithms has use in a large number of other maximization problems. We now formally state the algorithm Round&Scale and prove its correctness and running time.

\underline{Round&Scale (N, B)}

For each $i$ set $p_{i}^{'} = ⌊ \frac{n}{ϵ} \frac{1}{p_{max}} p_{i} ⌋$
Run exact algorithm with run time $O (n P^{'})$ to obtain $A$
Output $A$

Theorem 3.6. Round&Scale gives a

(1 - ϵ)

approximation and runs in

O (\frac{n^{3}}{ϵ})

time.

Proof. The rounding can be done in linear time and as

P^{'} = O (\frac{n^{2}}{ϵ})

, the dynamic programing portion of the algorithm runs in

O (\frac{n^{3}}{ϵ})

time. To show the approximation ratio, let

α = \frac{n}{ϵ} \frac{1}{p_{max}}

and let

A

be the solution returned by the algorithm and

A^{*}

be the optimal solution. Observe that for all

X \subseteq N

α p (X) - | X | \leq p^{'} (X) \leq α p (X)

as the rounding lowers each scaled profit by at most 1. The algorithm returns the best choice for

A

given the scaled and rounded values, so we know

p^{'} (A) \geq p^{'} (A^{*})

p (A) \geq \frac{1}{α} p^{'} (A) \geq \frac{1}{α} p^{'} (A^{*}) \geq p (A^{*}) - \frac{n}{α} = OPT - ϵ p_{max} \geq (1 - ϵ) OPT

It should be noted that this is not the best

FPTAS

known for Knapsack. In particular, ^[1] shows a

FPTAS

that runs in

O (n \log (1 / ϵ) + 1 / ϵ^{4})

time. There have been several improvements and we refer the reader to Chan's paper for the latest ^[2].

3.2 Other Problems

There are many variants of Knapsack and it is a fundamental problem of interest in integer programming as well in several other areas. One can find a book length treatment in ^[3]. We close with an interesting variant.

Multiple Knapsack: The input now consists of

m

knapsacks with capacities

B_{1}, B_{2}, \dots, B_{m}

and

n

items with sizes and profits as in Knapsack. We again wish to pack items to obtains as large a profit as possible, except now we have more than one knapsack with which to do so. An interesting special case is when all the knapsack capacities are the same quantity

B

which is related to the well known Bin Packing problem.

Eugene L Lawler. “Fast approximation algorithms for knapsack problems”. In: Mathematics of Operations Research 4.4 (1979), pp. 339–356. ↩︎
Timothy M Chan. “Approximation schemes for 0-1 knapsack”. In: 1st Symposium on Simplicity in Algorithms (SOSA 2018). Schloss DagstuhlLeibniz-Zentrum fuer Informatik. 2018. ↩︎
H. Kellerer, H.K.U.P.D. Pisinger, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer Nature Book Archives Millennium. Springer, 2004. isbn:9783540402862. url: https://books.google.com/books?id=u5DB7gck08YC. ↩︎