Computer Science – Data Structures and Algorithms
Scientific paper
2006-07-11
Computer Science
Data Structures and Algorithms
12 pages, 3 figures
Scientific paper
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 by Csirik et. al.
Han Xin
Iwama Kazuo
Ye Deshi
Zhang Guochuan
No associations
LandOfFree
Strip Packing vs. Bin Packing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Strip Packing vs. Bin Packing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strip Packing vs. Bin Packing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-138056