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 条
  • [41] Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing
    Henning, Soeren
    Jansen, Klaus
    Rau, Malin
    Schmarje, Lars
    COMPUTER SCIENCE - THEORY AND APPLICATIONS, CSR 2018, 2018, 10846 : 169 - 180
  • [42] A note on the Kenyon-Remila strip-packing algorithm
    Sviridenko, Maxim
    INFORMATION PROCESSING LETTERS, 2012, 112 (1-2) : 10 - 12
  • [43] Improved metaheuristics for the two-dimensional strip packing problem
    Rakotonirainy, Rosephine G.
    van Vuuren, Jan H.
    APPLIED SOFT COMPUTING, 2020, 92
  • [44] Algorithms for on-line strip packing
    Csirik, J
    Woeginger, GJ
    INFORMATION PROCESSING LETTERS, 1997, 63 (04) : 171 - 175
  • [45] Online strip packing with modifiable boxes
    Imreh, C
    OPERATIONS RESEARCH LETTERS, 2001, 29 (02) : 79 - 85
  • [46] Approximation algorithms for a hierarchically structured bin packing problem
    Codenotti, B
    De Marco, G
    Leoncini, M
    Montangero, M
    Santini, M
    INFORMATION PROCESSING LETTERS, 2004, 89 (05) : 215 - 221
  • [47] Approximation and online algorithms for multidimensional bin packing: A survey
    Christensen, Henrik I.
    Khan, Arindam
    Pokutta, Sebastian
    Tetali, Prasad
    COMPUTER SCIENCE REVIEW, 2017, 24 : 63 - 79
  • [48] Linear time-approximation algorithms for bin packing
    Zhang, GC
    Cai, XQ
    Wong, CK
    OPERATIONS RESEARCH LETTERS, 2000, 26 (05) : 217 - 222
  • [49] Approximation algorithms for the integrated path and bin packing problem
    Li, Weidong
    Sun, Ruiqing
    RAIRO-OPERATIONS RESEARCH, 2025, 59 (01) : 325 - 333
  • [50] A sublinear-time approximation scheme for bin packing
    Batu, Tugkan
    Berenbrink, Petra
    Sohler, Christian
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (47-49) : 5082 - 5092
12345