Harmonic algorithm for 3-dimensional strip packing problem

N. Bansal, X. Han, K. Iwama, M. Sviridenko, G. Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

17 Citations (Scopus)

Abstract

In the three dimensional strip packing problem, we are given a set of three-dimensional rectangular items I = {(xi, yi, zi) : i = 1, ..., n} and a three dimensional box B. The goal is to pack all the items in the box B without any overlap, such that the height of the packing is minimized. We consider the most basic version of the problem, where the items must be packed with their edges parallel to the edges of B and cannot be rotated. Building upon Caprara's work [4] for the two dimensional bin packing problem we obtain an approximation algorithm with a similar performance guarantee of T8 ≈ 1.69 where T8 is the well known Harmonic number that occurs naturally in the context of bin packing. The previously known approximation algorithms for this problem had worst case performance guarantees of 2 [7], 2.64 [14], 2.67 [15], 2.89 [10] and 3.25 [11]. Our second algorithm is an asymptotic PTAS for the case in which all items have square bases.
Original languageEnglish
Title of host publicationProceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07, New Orleans LA, USA, January 7-9, 2007)
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages1197-1206
ISBN (Print)978-0-898716-24-5
DOIs
Publication statusPublished - 2007
Externally publishedYes

Fingerprint Dive into the research topics of 'Harmonic algorithm for 3-dimensional strip packing problem'. Together they form a unique fingerprint.

Cite this