A (5/3+ε)-Approximation for Strip Packing

被引：0
|
作者：
Harren, Rolf [1 ]
Jansen, Klaus [2 ]
Praedel, Lars [2 ]
van Stee, Rob [1 ]
机构：
[1] MPII, Campus El 4, D-66123 Saarbrucken, Germany
[2] Univ Kiel, Inst Informat, D-24118 Kiel, Germany
来源：
ALGORITHMS AND DATA STRUCTURES | 2011年 / 6844卷
关键词：
strip packing; rectangle packing; approximation algorithm; absolute worst-case ratio; TWO-DIMENSIONAL PACKING; PERFORMANCE BOUNDS; BIN PACKING; ALGORITHMS; RECTANGLE;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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 approximation ratio of 5/3 + epsilon for any epsilon > 0. This result significantly narrows the gap between the best known upper bounds of 2 by Schiermeyer and Steinberg and 1.9396 by Harren and van Stee and the lower bound of 3/2.
引用
收藏
页码：475 / +
页数：3
相关论文
共 50 条
  • [1] A (5/3+ε)-approximation for strip packing
    Harren, Rolf
    Jansen, Klaus
    Praedel, Lars
    van Stee, Rob
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2014, 47 (02): : 248 - 267
  • [2] A Tight (3/2+ε)-Approximation for Skewed Strip Packing
    Galvez, Waldo
    Grandoni, Fabrizio
    Ameli, Afrouz Jabal
    Jansen, Klaus
    Khan, Arindam
    Rau, Malin
    ALGORITHMICA, 2023, 85 (10) : 3088 - 3109
  • [3] Improved approximation for two dimensional Strip Packing with polynomial bounded width
    Jansen, Klaus
    Rau, Malin
    THEORETICAL COMPUTER SCIENCE, 2019, 789 : 34 - 49
  • [4] Improved Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width
    Jansen, Klaus
    Rau, Malin
    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, 2017, 10167 : 409 - 420
  • [5] Approximate strip packing: Revisited
    Han, Xin
    Iwama, Kazuo
    Ye, Deshi
    Zhang, Guochuan
    INFORMATION AND COMPUTATION, 2016, 249 : 110 - 120
  • [6] Approximation Algorithms for Multiple Strip Packing
    Bougeret, Marin
    Dutot, Pierre Francois
    Jansen, Klaus
    Otte, Christina
    Trystram, Denis
    APPROXIMATION AND ONLINE ALGORITHMS, 2010, 5893 : 37 - +
  • [7] A New Asymptotic Approximation Algorithm for 3-Dimensional Strip Packing
    Jansen, Klaus
    Praedel, Lars
    SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2014, 8327 : 327 - 338
  • [8] An approximation scheme for strip packing of rectangles with bounded dimensions
    de la Vega, WF
    Zissimopoulos, V
    DISCRETE APPLIED MATHEMATICS, 1998, 82 (1-3) : 93 - 101
  • [9] Absolute approximation ratios for packing rectangles into bins
    Harren, Rolf
    van Stee, Rob
    JOURNAL OF SCHEDULING, 2012, 15 (01) : 63 - 75
  • [10] Absolute approximation ratios for packing rectangles into bins
    Rolf Harren
    Rob van Stee
    Journal of Scheduling, 2012, 15 : 63 - 75
12345