Journal
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
Volume 47, Issue 2, Pages 248-267Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.comgeo.2013.08.008
Keywords
Strip packing; Rectangle packing; Approximation algorithm; Absolute worst-case ratio
Categories
Ask authors/readers for more resources
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 + epsilon for any epsilon > 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. (C) 2013 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available