### Bin packing in multiple dimensions: Inapproximability results and approximation schemes

### Abstract

We study the following packing problem: Given a collection of d-dimensional rectangles of specified sizes, pack them into the minimum number of unit cubes. We show that unlike the one-dimensional case, the two-dimensional packing problem cannot have an asymptotic polynomial time approximation scheme (APTAS). unless P = NP. On the positive side, we give an APTAS for the special case of packing d-dimensional cubes into the minimum number of unit cubes. Second, we give a polynomial time algorithm for packing arbitrary two-dimensional rectangles into at most OPT square bins with sides of length 1 + Îµ, where OPT denotes the minimum number of unit bins required to pack these rectangles. Interestingly, this result has no additive constant term, i.e., is not an asymptotic result. As a corollary, we obtain the first approximation scheme for the problem of placing a collection of rectangles in a minimum-area encasing rectangle. Â© 2006 INFORMS.

### Más información

Título según WOS: | Bin packing in multiple dimensions: Inapproximability results and approximation schemes |

Título según SCOPUS: | Bin packing in multiple dimensions: Inapproximability results and approximation schemes |

Título de la Revista: | MATHEMATICS OF OPERATIONS RESEARCH |

Volumen: | 31 |

Número: | 1 |

Editorial: | INFORMS |

Fecha de publicación: | 2006 |

Página de inicio: | 31 |

Página final: | 49 |

Idioma: | English |

URL: | http://pubsonline.informs.org/doi/abs/10.1287/moor.1050.0168 |

DOI: |
10.1287/moor.1050.0168 |

Notas: | ISI, SCOPUS |