New Upper Bounds on The Approximability of 3D Strip Packing

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

In this paper, we study the 3D strip packing problem in which we are given a list of 3-dimensional boxes and required to pack all of them into a 3-dimensional strip with length 1 and width 1 and unlimited height to minimize the height used. Our results are below: i) we give an approximation algorithm with asymptotic worst-case ratio 1.69103, which improves the previous best bound of $2+ε$ by Jansen and Solis-Oba of SODA 2006; ii) we also present an asymptotic PTAS for the case in which all items have {\em square} bases.
Submitted to SODA 2007

Keywords

Data Structures and Algorithms

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/113569

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0607100
 http://arxiv.org/abs/cs/0607100

Collections

arXiv