Chapter 8
Bin Packing
Here we consider the classical Bin Packing problem: We are given a set I = {1, . . . , n} of
items, where item i ∈ I has size si ∈ (0, 1] and a set B = {1, . . . , n} of bins with capacity
one. Find an assignment a : I → P B such that the number of non-empty bins is minimal.
As a shorthand, we write s(J) = j∈J sj for any J ⊆ I.
8.1 Hardness of Approximation
The Bin Packing problem is NP-complete. More specifically:
Theorem 8.1. It is NP-complete to decide if an instance of Bin Packing admits a
solution with two bins.
Proof. We reduce from Partition, which we know is NP-complete. Recall that in the
Partition problem, we are given n numbers P c1 , .P
. . , cn ∈ N and are asked to decide if
there is a set S ⊆ {1, . . . , n} such that i∈S ci = i6∈S ci . Given P a Partition instance,
we create an instance for Bin Packing by setting si = 2ci /( nj=1 cj ) ∈ (0, 1] for i =
1, . . . , n. Obviously
P P two bins suffice if and only if there is a S ⊆ {1, . . . , n} such that
i∈S ci = i6∈S ci .
This allows us to derive a lower bound on the approximabilty of Bin Packing.
Corollary 8.2. There is no ρ-approximation algorithm with ρ < 3/2 for Bin Packing
unless P = NP.
8.2 Heuristics
We will show that there are constant factor approximations for Bin Packing. Firstly
we consider the probably most simple Next Fit algorithm, which can be shown to be
2-approximate. Secondly, we give the First Fit Decreasing algorithm and show that
it is 3/2-approximate. Thus, with the above hardness result, this is best-possible, unless
P = NP.
Next Fit
The Next Fit algorithm works as follows: Initially all bins are empty and we start with
bin j = 1 and item i = 1. If bin j has residual capacity for item i, assign item i to bin j,
i.e., a(i) = j, and consider item i + 1. Otherwise consider bin j + 1 and item i. Repeat
until item n is assigned.
56
Theorem 8.3. Next Fit is a 2-approximation for Bin Packing. The algorithm runs
in O (n) time.
Proof. Let k be the number of non-empty bins in the assignment a found by Next Fit.
Let k ∗ be the optimal number of bins. We show the slightly stronger statement that
k ≤ 2 · k ∗ − 1.
Firstly we observe the lower bound k ∗ ≥ ⌈s(I)⌉. Secondly, for bins j = 1, . . . , ⌊k/2⌋ we
have X
si > 1.
i:a(i)∈{2j−1,2j}
Adding these inequalities we get
k
< s(I).
2
Since the left hand side is an integer we have that
k−1 k
≤ ≤ ⌈s(I)⌉ − 1.
2 2
This proves k ≤ 2 · ⌈s(I)⌉ − 1 ≤ 2 · k ∗ − 1 and hence the claim.
The analysis is tight for the algorithm, which can be seen with the following instance
with 2n items. For some ε > 0 let s2i−1 = 2 · ε, s2i = 1 − ε for i = 1, . . . , n.
First Fit Decreasing
The algorithm Next Fit never considers bins again that have been left behind. Thus
the wasted capacity therein leaves room for improvement. A natural way is First Fit:
Initially all bins are empty and we start with current number of bins k = 0 and item i = 1.
Consider all bins j = 1, . . . , k and place item i in the first bin that has sufficient residual
capacity, i.e., a(i) = j. If there is no such bin increment k and repeat until item n is
assigned. One can prove that First Fit uses at most k ≤ ⌈17/10 · k ∗ ⌉ many bins, where
k ∗ is the optimal number.
There is a further natural heuristic improvement of First Fit, called First Fit
Decreasing: Reorder the items such that s1 ≥ · · · ≥ sn and apply First Fit. The
intuition behind considering large items first is the following: “Large” items do not fit into
the same bin anyway, so we already use unavoidable bins and try to place “small” items
into the residual space.
Theorem 8.4. First Fit Decreasing is a 3/2-approximation for Bin Packing. The
algorithm runs in O n2 time.
Proof. Let k be the number of non-empty bins of the assignment a found by First Fit
Decreasing and let k ∗ be the optimal number.
Consider bin number j = ⌈2/3k⌉. If it contains an item i with si > 1/2, then each bin
j ′ < j did not have space for item i. Thus j ′ was assigned an item i′ with i′ < i. As the
items are considered in non-increasing order of size we have si′ ≥ si > 1/2. That is, there
are at least j items of size larger than 1/2. These items need to be placed in individual
bins. This implies
2
k ∗ ≥ j ≥ k.
3
57
Otherwise, bin j and any bin j ′ > j does not contain an item with size larger than 1/2.
Hence the bins j, j + 1, . . . , k contain at least 2(k − j) + 1 items, none of which fits into
the bins 1, . . . , j − 1. Thus we have
s(I) > min{j − 1, 2(k − j) + 1}
≥ min{⌈2/3k⌉ − 1, 2(k − (2/3k + 2/3)) + 1}
= ⌈2/3k⌉ − 1
and k ∗ ≥ s(I) > ⌈2/3k⌉ − 1. This even implies
2 2
k∗ ≥ k ≥ k
3 3
and hence the claim.
8.3 Asymptotic Polynomial Time Approximation Scheme
With the hardness result that there is no approximation algorithm for Bin Packing with
guarantee better than 3/2, unless P = NP, we do not have to search for a PTAS (or even
an FPTAS). However, notice that the reduction used that the optimal number of bins is
“small”, such as 2 or 3. It is plausible that, in “practical” instances, the optimal number
k ∗ of bins grows as the number of items grows. Maybe we can do better for those instances.
This leads us to define: An asymptotic polynomial time approximation scheme (AP-
TAS) is a familiy of algorithms, such that for any ε > 0 there is a number k ′ and a
(1 + ε)-approximation algorithm, whenever k ∗ ≥ k ′ . For Bin Packing such a family
exists. However, the involved running times are rather high, even though polynomial in n.
Theorem 8.5. For any 0 < ε ≤ 1/2 there is an algorithm that runs in time polynomial
in n and finds an assignment having at most k ≤ (1 + ε) · k ∗ + 1 many bins.
Lemma 8.6. Let ε > 0 and d ∈ N be constants. For any instance of Bin Packing where
si ≥ ε and |{s1 , . . . , sn }| ≤ d, there is a polynomial time algorithm that solves it optimally.
Proof. The number of items in a bin is bounded by m := ⌊1/ε⌋. Therefore, the number
of different assignments for one bin is bounded by r = m+d
m , which is a (large) constant.
There are at most n bins used and therefore, the number of feasible assignments is bounded
by p = n+r r . This is a polynomial in n. Thus we can enumerate all assignments and
choose the best one to give an optimum solution.
Lemma 8.7. Let ε > 0 be a constant. For any instance of Bin Packing where si ≥ ε,
there is a (1 + ε)-approximation algorithm.
Proof. Let I be the given instance. Sort the n items by increasing size and partition them
into g = ⌈1/ε2 ⌉ many groups each having at most q = ⌊nε2 ⌋ many items. Notice that two
groups may contain items of the same size.
Construct an instance J by rounding up the size of each item to the size of the largest
item in its group. Instance J has at most g many different item sizes. Therefore, we
can find an optimal assignment for J by invoking Lemma 8.6. This is clearly a feasible
assignment for the original item sizes.
Now we show that k ∗ (J) ≤ (1 + ε)k ∗ (I): We construct another instance J ′ by rounding
down the size of each item to the smallest item size in its group. Clearly k ∗ (J ′ ) ≤ k ∗ (J).
58
The crucial observation is that an assignment for instance J ′ yields an assignment for all
but the largest q items of the instance J. Therefore
k ∗ (J) ≤ k ∗ (J ′ ) + q ≤ k ∗ (I) + q.
To finalize the proof, since each item has size at least ε, we have k ∗ (I) ≥ n · ε and
q = ⌊nε2 ⌋ ≤ ε · k ∗ (I). Hence
k ∗ (J) ≤ (1 + ε) · k ∗ (I)
and the claim is established.
Proof of Theorem 8.5. Let I denote the given instance and I ′ the instance after discarding
the items with size less than ε from I. We can invoke Lemma 8.7 and find an assignment
which uses at most k(I ′ ) ≤ (1 + ε) · k ∗ (I ′ ) many bins. By using First Fit, we assign the
items with sizes less than ε into the solution found for instance I ′ . We use additional bins
if an item does not fit into any of the bins used so far.
If no additional bins are needed, then our assignment uses k(I) ≤ (1 + ε) · k ∗ (I ′ ) ≤
(1 + ε) · k ∗ (I) many bins. Otherwise, all but the last bin have residual capacity less than
ε. Thus s(I) ≥ (k(I) − 1)(1 − ε), which is a lower bound for k ∗ (I). Thus we have
k ∗ (I)
k(I) ≤ + 1 ≤ (1 + 2ε) · k ∗ (I) + 1,
1−ε
where we have used 0 < ε ≤ 1/2.
59
