New Upper Bounds on The Approximability of 3D Strip Packing
<|reference_start|>New Upper Bounds on The Approximability of 3D Strip Packing: 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+\epsilon$ 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.<|reference_end|>
@article{han2006new,
    title={New Upper Bounds on The Approximability of 3D Strip Packing},
    author={Xin Han, Kazuo Iwama, Guochuan Zhang},
    journal={arXiv preprint arXiv:cs/0607100},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0607100},
    primaryClass={cs.DS}
}