New Upper Bounds on The Approximability of 3D Strip Packing
| dc.creator | Han, Xin | |
| dc.creator | Iwama, Kazuo | |
| dc.creator | Zhang, Guochuan | |
| dc.date | 2006-07-22 | |
| dc.date.accessioned | 2026-07-07T07:16:22Z | |
| dc.date.available | 2026-07-07T07:16:22Z | |
| dc.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. | |
| dc.description | Submitted to SODA 2007 | |
| dc.identifier | https://arxiv.org/abs/cs/0607100 | |
| dc.identifier | http://arxiv.org/abs/cs/0607100 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/113569 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | New Upper Bounds on The Approximability of 3D Strip Packing | |
| dc.type | text |