Resource augmentation in two-dimensional packing with orthogonal rotations

Correa JR

Abstract

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90° rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1+ε), for any positive ε. Additionally, we show near-optimal packing results for a number of related packing problems. © 2005 Elsevier B.V. All rights reserved.

Más información

Título según WOS: Resource augmentation in two-dimensional packing with orthogonal rotations
Título según SCOPUS: Resource augmentation in two-dimensional packing with orthogonal rotations
Título de la Revista: OPERATIONS RESEARCH LETTERS
Volumen: 34
Número: 1
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2006
Página de inicio: 85
Página final: 93
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0167637705000337
DOI:

10.1016/j.orl.2005.02.005

Notas: ISI, SCOPUS