BITS, PILANI – K. K.
BIRLA GOA CAMPUS
Design & Analysis of Algorithms
(CS F364)
Lecture No. 30
1
Re Cap 0-1 Knapsack
Greedy Algorithm Modified
𝒗𝒊
1. Sort items in non-increasing order of
𝒘𝒊
2. Greedily add items until we hit an item (say kth
item) that is too big, that is σ𝑘𝑖=1 𝑤𝑖 ≥ W
3. Pick the better of {1, 2,….,k-1} and {k}
Theorem:
Greedy Algorithm Modified is a 2-approximation
algorithm for the 0-1 knapsack problem
Bin Packing
You are given n items, of sizes s1, s2,…..,sn
All sizes are such that 0 < si ≤ 1.
There is infinite supply of unit size bins.
Goal:
To pack the items in as few bins as possible
Example:
Is this packing optimal?
Bin Packing
Optimal Packing
Bin Packing
We define that a bin is open if we can put item into it; otherwise, it
is defined as closed.
Next Fit Algorithm
The first item s1 is placed into bin B1.
Let Bj be the last used bin,
when the algorithm considers item si: it assigns si to Bj if Bj has
enough room, otherwise, closes Bj and assigns si to a new bin Bj+1
Example
.
Bin Packing
Theorem:
The approximation ratio for Next Fit is 2.
Proof:
Suppose that Next Fit uses h bins & optimal algorithm
uses h* bins.
Observe:
• The sum of items sizes in each consecutive bins is
greater than 1
(otherwise, we can put them together)
• 𝒉∗ ≥ ⎾ σ𝒏𝒊=𝟏 𝒔𝒊 ⏋ (1)
Bin Packing
Case 1: h is even
C(B1) + C(B2) ≥ 1
+C(B3) + C(B4) ≥ 1
……..
+C(Bh-1) + C(Bh) ≥ 1
Therefore, σ𝒏𝒊=𝟏 𝒔𝒊 ≥ h/2
which implies 𝒉 ≤ 𝟐 σ 𝒔𝒊 (2)
Using Equations (1) and (2) we get
h ≤ 2h*
Bin Packing
Case 2: h is odd
C(B1) + C(B2) ≥ 1
+C(B3) + C(B4) ≥ 1
……..
+C(Bh-2) + C(Bh-1) ≥ 1
Therefore, σ 𝒔𝒊 ≥ (h-1)/2 + C(Bh)
Therefore, ⎾𝟐 σ 𝒔𝒊 ⏋≥ ⎾(h – 1) + 2C(Bh)⏋
Therefore, ⎾𝟐 σ 𝒔𝒊 ⏋≥ h
Therefore, h ≤ ⎾𝟐 σ 𝒔𝒊 ⏋≤ 2 ⎾ σ 𝒔𝒊 ⏋≤ 2 h*
Therefore , Next Fit is 2-approximation algorithm
Exercise: Show that 2 is a tight bound
Bin Packing
Algorithm : First Fit
1. Place the items in the order in which they arrive.
2. Place the next item into the lowest numbered bin in
which it fits.
3. If it does not fit into any open bin, start a new bin.
Example:
First Fit algorithm returns a solution h such that h ≤ 1.7h* + 2
Offline Algorithm
A disadvantage with online algorithms is that packing
large items is difficult, especially if they occur late in
the sequence
If we can view the entire sequence upfront, we should
expect to do better.
Algorithm : First Fit Decreasing
1. Sorts the items in non-increasing order with regards
to their sizes
2. Process as First Fit.
First Fit Decreasing algorithm is a 3/2-approximation
for Bin Packing
Proof - Idea
Let k be the number of non-empty bins found by First Fit
Decreasing and let k* be the optimal number.
Consider bin number j = ⌈2/3k⌉.
Suppose 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.
Since the items are considered in non-increasing order of size we
have si’ ≥ si > 1/2.
Therefore, there are at least j items of size larger than 1/2.
And these items need to be placed in individual bins.
This implies k* ≥ j ≥ 2/3 k.
Proof
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}, where 𝒔 𝑰 = σ𝒊 ∈𝑰 𝒔𝒊
≥ ⌈2/3k⌉ − 1
Also, k* ≥ s(I)
Therefore, k* ≥ ⌈2/3k⌉ ≥ 2/3k
Bin Packing
Question
Does there exist ρ-approximation algorithm with ρ< 3/2
Like in the case of TSP we can show:
If P ≠ NP, there can not exist a ρ-approximation
algorithm for the bin packing problem for any ρ < 3/2
We use Set Partition Problem for proving the above
theorem.
