Next: MINIMUM HEIGHT TWO DIMENSIONAL
Up: Data Storage
Previous: Data Storage
  Index
- 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
Viggo Kann
1999-04-22