SR1 M INIMUM B IN P ACKING

       
• I NSTANCE : Finite set U of items, a size for each , and a positive integer bin capacity B .
• S OLUTION : A partition of U into disjoint sets such that the sum of the a partition of U such that the sum of the items in each is B or less.
• M EASURE : The number of used bins, i.e., the number of disjoint sets, m .

• Good News: Approximable within 3/2 [ 322 ] and within 71/60 [ 196 ], [ 349 ].
• Bad News: Not approximable within 3/2 for any [ 121 ].
• Comment: Admits an , that is, is approximable within in time polynomial in , where [ 208 ]. A PX -intermediate unless the polynomial-hierarchy collapses [ 85 ]. A survey of approximation algorithms for M INIMUM B IN P ACKING is found in [ 81 ]. 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 [ 343 ], and is not in [ 301 ]. 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 [ 11 ]. 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 [ 189 ] and not approximable within for a given in the general case [ 264 ].
• Garey and Johnson: SR1