Harren, Rolf, Jansen, Klaus, Praedel, Lars and van Stee, Rob (2014) A (5/3+epsilon)-approximation for strip packing. Computational Geometry-Theory and Applications, 47 (2). pp. 248-267. DOI 10.1016/j.comgeo.2013.08.008.

Full text not available from this repository.

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 + 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.

Document Type:	Article
Additional Information:	Times Cited: 0 B 12th International Symposium on Algorithms and Data Structures (WADS) AUG 15-17, 2011 New York Univ, Polytechn Inst, New York, NY 0
Keywords:	Strip packing, Rectangle packing, Approximation algorithm, Absolute worst-case ratio
Research affiliation:	Kiel University > Kiel Marine Science OceanRep > The Future Ocean - Cluster of Excellence Kiel University
Refereed:	Yes
Open Access Journal?:	No
Publisher:	Elsevier
Projects:	Future Ocean
Date Deposited:	30 Mar 2015 12:19
Last Modified:	23 Aug 2019 08:56
URI:	https://oceanrep.geomar.de/id/eprint/27708

Actions (login required)

View Item