Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-112 | 22nd August 2006 00:00

Strip Packing vs. Bin Packing


Authors: Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang
Publication: 31st August 2006 15:51
Downloads: 1664


In this paper
we establish a general algorithmic framework between bin packing
and strip packing, with which we achieve the same asymptotic
bounds by applying bin packing algorithms to strip packing. More
precisely we obtain the following results: (1) Any offline bin
packing algorithm can be applied to strip packing maintaining the same
asymptotic worst-case ratio. Thus using FFD (MFFD) as a subroutine,
we get a practical (simple and fast) algorithm
for strip packing with an upper bound 11/9 (71/60).
A simple AFPTAS for strip
packing immediately follows.
(2) A class of Harmonic-based
algorithms for bin packing can be applied to online strip packing
maintaining the same asymptotic competitive ratio. It implies
online strip packing admits an upper bound of 1.58889
on the asymptotic competitive ratio,
which is very close to the lower bound 1.5401
and significantly improves
the previously best bound of 1.6910 and affirmatively answers an
open question posed \cite{cw97}.

ISSN 1433-8092 | Imprint