MINIMUM BIN PACKING

• INSTANCE: Finite set U of items, a size $s(u)\in Z^+$ for each $u\in U$, and a positive integer bin capacity B.

• SOLUTION: A partition of U into disjoint sets $U_1, U_2,\ldots, U_m$ such that the sum of the items in each $U_i$ is B or less.

• MEASURE: The number of used bins, i.e., the number of disjoint sets, m.

  
  

• Good News: Approximable within 3/2 [442] and within 71/60 $+\frac{78}{71\mbox{\sl opt}}$ [278], [474].

• Bad News: Not approximable within 3/2$-\varepsilon$ for any $\varepsilon >0$ [182].

• Comment: Admits an $\mbox{\sc FPTAS}^\infty$, that is, is approximable within $1+\varepsilon$ in time polynomial in $1/\varepsilon$, where $\varepsilon =O(\log^2(\mbox{\sl opt})/\mbox{\sl opt})$ [292]. APX-intermediate unless the polynomial-hierarchy collapses [125]. A survey of approximation algorithms for MINIMUM BIN PACKING is found in [120]. If a partial order on U is defined and we require the bin packing to obey this order, then the problem is approximable within 2 [464], and is not in $\mbox{\sc FPTAS}^\infty$ [410]. The generalization in which the cost of a bin is a monotone and concave function of the number of items in the bin is approximable within 7/4 and is not approximable within 4/3 unless some information about the cost function is used [24]. The generalization of this problem in which a conflict graph is given such that adjacent items are assigned to different bins is approximable within 2.7 for graphs that can be colored in polynomial time [271] and not approximable within $\vert U\vert^{\varepsilon }$ for a given $\varepsilon$ in the general case [365].

• Garey and Johnson: SR1