A (5/3+epsilon)-approximation for strip packing

作者：Harren Rolf; Jansen Klaus; Praedel Lars; van Stee Rob

来源：Computational Geometry-Theory and Applications, 2014, 47(2): 248-267.

DOI：10.1016/j.comgeo.2013.08.008

• Strip packing
• Rectangle packing
• Approximation algorithm
• Absolute worst-case ratio

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.

• 出版日期2014-2