CS 3343, Bin Packing, Approximation

CS 3343
Analysis of Algorithms
Weird Topic

Bin Packing
Approximation

Bin-Packing Problem (BP): Start with a positive integer bin size denoted by W, and a finite set of positive integers {b₁, b₂, ...} which are item sizes of items to packed into a succession of bins. A bin packing is an assignment of each each item to a bin in such a way that the sum of the item sizes for items in each bin is less than or equal to W. The decision question is: Given an integer k, is there a bin-packing using k bins?

Bin-Packing Problem (BP):

Start with a positive integer bin size denoted by W, and a finite set of positive integers {b₁, b₂, ...} which are item sizes of items to packed into a succession of bins. A bin packing is an assignment of each each item to a bin in such a way that the sum of the item sizes for items in each bin is less than or equal to W.

The decision question is: Given an integer k, is there a bin-packing using k bins?

This problem is known to be NP-complete. An exact optimal solution seems difficult, but there are two approximation algorithms for solving this problem. The second one gives quite good results, as described below.

First Fit (FF) Approximation Algorithm: Start with the items in an arbitrary order, perhaps their order of occurrence, and with an ordered sequence of empty bins. Place each successive item into the first bin into which it will fit. Check if the number of non-empty bins is less than or equal to k.

First Fit (FF) Approximation Algorithm:

Start with the items in an arbitrary order, perhaps their order of occurrence, and with an ordered sequence of empty bins. Place each successive item into the first bin into which it will fit. Check if the number of non-empty bins is less than or equal to k.

For a problem instance I, let OPT(I) denote the number of bins required in an optimal solution, and let FF(I) be the number of bins using FF. The following result can be proved about the performance of FF:

FF(I) <= (17 / 11) * Opt(I) + 1

The following example shows that the bound of 17 / 10 can't be improved:

Click box or here for full size image.

The second algorithm is a simple refinement of FF:

First Fit Decreasing (FFD) Approximation Algorithm: The same as FF, except that we start with the items in non-increasing order.

First Fit Decreasing (FFD) Approximation Algorithm:

The same as FF, except that we start with the items in non-increasing order.

Again for a problem instance I, we have the result:

FF(I) <= (11 / 9) * Opt(I) + 4

Again, the following example shows that the bound of 11 / 9 can't be improved:

Click box or here for full size image.

Both the results above were extremely difficult to prove.

Below is another example showing the difficulties one might encounter in trying to prove results about bin packing. This is an instance of the use of FFD in which a given set of items can be fit into 7 bins. But if the item of size 46 is deleted from the set, the same algorithm now requires 8 bins! (The figure gives 47 in place of 46 one time in error.)

Click box or here for full size image.

Revision date: 2012-11-29. (Please use ISO 8601, the International Standard Date and Time Notation.)