Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414290 | Computational Geometry | 2014 | 20 Pages |
Abstract
We study strip packing, which is one of the most classical two-dimensional packing problems: given a collection of rectangles, the problem is to find a feasible orthogonal packing without rotations into a strip of width 1 and minimum height. In this paper we present an approximation algorithm for the strip packing problem with absolute approximation ratio of 5/3+ε5/3+ε for any ε>0ε>0. This result significantly narrows the gap between the best known upper bound and the lower bound of 3/2; previously, the best upper bound was 1.9396 due to Harren and van Stee.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rolf Harren, Klaus Jansen, Lars Prädel, Rob van Stee,