Next: MINIMUM HEIGHT TWO DIMENSIONAL Up: Data Storage Previous: Data Storage Index

### MINIMUM BIN PACKING

- INSTANCE: Finite set U of items, a size for each , and a positive integer bin capacity B.

- SOLUTION: 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 Ui is B or less.

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

- Good News: Approximable within 3/2 [419] and within 71/60 [263], [450].

- Bad News: Not approximable within 3/2 for any [170].

- Comment: Admits an , that is, is approximable within in time polynomial in , where [277]. APX-intermediate unless the polynomial-hierarchy collapses [117]. A survey of approximation algorithms for MINIMUM BIN PACKING is found in [112]. 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 [441], and is not in [389]. 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 [23]. 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 [256] and not approximable within for a given in the general case [346].

- Garey and Johnson: SR1

Next: MINIMUM HEIGHT TWO DIMENSIONAL Up: Data Storage Previous: Data Storage Index