9.1.1. A Simple Greedy Algorithm

The following is probably the most natural greedy algorithm one can think of: Start by packing the first item \(s_1\) into a new bin \(B_1\). For every subsequent item \(s_i\), we check whether there exists a bin \(B_j\) such that \(\sum_{s \in B_j} s \le 1 - s_i\). If so, we choose an arbitrary such bin \(B_j\) and add \(s_i\) to \(B_j\). Otherwise, we create a new bin \(B_{k+1}\) (where \(k\) is the number of bins created so far) and add \(s_i\) to this new bin. Let us call this algorithm First Fit because it adds \(s_i\) to the first bin where it fits.

If we apply First Fit to the five items in the example in Figure 9.1, we use \(4\) bins, one more than the optimal number. First Fit places the first item into its own bin and then places the second item into the same bin because it fits. This fills the first bin to \(0.6 + 0.3 = 0.9\). Each of the remaining three items then needs to be packed into its own bin.

Figure 9.2: Coming soon!

In this example, the solution computed by First Fit is not optimal, but it is less than a factor \(2\) away from an optimal solution: The solution computed by First Fit uses \(4\) bins. The optimal solution uses \(3\) bins. Let us prove that this is true for every possible input:

Theorem 9.1: The First Fit algorithm computes a \(2\)-approximation for the bin packing problem.

Proof: As discussed in Section 8.2, the key to bounding the approximation ratio of the algorithm is to provide the right lower bound on the number of bins in an optimal solution. Here, a very simple lower bound is enough: The total size of the bins cannot be less than the total size of all items. Thus, since every bin has size \(1\), the optimal number of bins is \(\textrm{OPT} \ge \sum_{i=1}^n s_i\). We prove that First Fit uses at most \(2\sum_{i=1}^n s_i \le 2 \cdot \textrm{OPT}\) bins.

We group the bins into pairs. If the number of bins is odd, then the last bin is ignored in this grouping. Each pair of bins \((B_i, B_j)\) satisfies \(\sum_{s \in B_i \cup B_j} > 1\). Indeed, assume that \(i < j\) and let \(s_h\) be the first element in \(B_j\). If \(\sum_{s \in B_i \cup B_j} s \le 1\), then \(\sum_{s \in B_i} \le 1 - s_h\). Since this is true at the end of the algorithm, it is also true when the algorithm decides into which bin to place \(s_h\). On the other hand, since \(s_h\) is the first item we place into bin \(B_j\), \(s_h\) does not fit into any of the bins \(B_1, \ldots, B_{j-1}\) at the time we place \(s_h\) into bin \(B_j\). Since \(i < j\), this is a contradiction.

Since every pair of bins \((B_i, B_j)\) satisfies \(\sum_{s \in B_i \cup B_j} s > 1\). we have \(\sum_{i=1}^n s_i > p\), where \(p\) is the number of pairs of bins. Since \(\textrm{OPT} \ge \sum_{i=1}^n s_i\), this implies that \(\textrm{OPT} > p\), that is, \(\textrm{OPT} \ge p + 1\). The number of bins we use is at most \(2p + 1 < 2p + 2 \le 2 \cdot \textrm{OPT}\), that is, First Fit computes a \(2\)-approximation of the optimal number of bins. ▨