9.1.2. A Family of Tight Inputs

Recall that once we have an approximation algorithm for an NP-hard optimization problem, we should ask the question whether the approximation ratio achieved by our algorithm is the best possible. We will do this for some problems in these notes, but not for all of them. Also recall that this question comes in two flavours. The harder question is whether there exists any algorithm that achieves a better approximation ratio than our algorithm. The easier question is whether the analysis of our algorithm is tight, whether it does in fact achieve a better approximation ratio than we were able to prove.

For the bin packing problem, we consider the second question. It turns out that our analysis is not tight. It has been shown fairly recently that First Fit achieves an approximation ratio of \(1.7\) and that this analysis is in fact tight, that is, that there exists an infinite family of inputs for which First Fit does indeed produce a solution that is \(1.7\) times worse than an optimal solution. This analysis of First Fit requires some care though. Here, we will be content with proving that there exists an infinite family of inputs for which First Fit computes a solution that is \(\frac{5}{3} \approx 1.667\) times worse than an optimal solution.

Consider an input consisting of \(18n\) items, shown in Figure 9.3. The first \(6n\) items have size \(0.15\), the next \(6n\) items have size \(0.34\), and the final \(6n\) items have size \(0.51\). One item of size \(0.15\), one item of size \(0.34\), and one item of size \(0.51\) fit in a bin, since their combined size is exactly \(1\). Thus, \(\textrm{OPT} = 6n\). First Fit packs the first \(6n\) items into \(n\) bins, packing \(6\) items into each bin. This uses \(0.9\) space in each of these \(n\) bins, that is none of these bins can accommodate any further items. The next \(6n\) items are packed into \(3n\) bins, \(2\) items per bin. This uses \(0.68\) space in each of these \(3n\) bins, that is none of these bins can accommodate any of the remaining items of size \(0.51\). Thus, the final \(6n\) items are packed into one bin each, using \(6n\) bins in total. Therefore, First Fit uses \(10n\) bins in total. This is a \(\frac{5}{3}\)-approximation of the optimal number of bins, which is \(6n\).

Figure 9.3: Coming soon!