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 条
  • [31] Approximation Schemes for Packing with Item Fragmentation
    Hadas Shachnai
    Tami Tamir
    Omer Yehezkely
    Theory of Computing Systems, 2008, 43 : 81 - 98
  • [32] Approximation schemes for packing with item fragmentation
    Shachnai, Hadas
    Tamir, Tami
    Yehezkely, Omer
    THEORY OF COMPUTING SYSTEMS, 2008, 43 (01) : 81 - 98
  • [33] A note on online strip packing
    Deshi Ye
    Xin Han
    Guochuan Zhang
    Journal of Combinatorial Optimization, 2009, 17 : 417 - 423
  • [34] Peak Demand Minimization via Sliced Strip Packing
    Deppert, Max A.
    Jansen, Klaus
    Khan, Arindam
    Rau, Malin
    Tutas, Malte
    ALGORITHMICA, 2023, 85 (12) : 3649 - 3679
  • [35] An effective shaking procedure for 2D and 3D strip packing problems
    Wauters, Tony
    Verstichel, Jannes
    Vanden Berghe, Greet
    COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (11) : 2662 - 2669
  • [36] Closing the Gap for Pseudo-Polynomial Strip Packing
    Jansen, Klaus
    Rau, Malin
    27TH ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS (ESA 2019), 2019, 144
  • [37] Techniques and results on approximation algorithms for packing circles
    Miyazawa, Flavio K.
    Wakabayashi, Yoshiko
    SAO PAULO JOURNAL OF MATHEMATICAL SCIENCES, 2022, 16 (01): : 585 - 615
  • [38] Improved Approximation Algorithms for Bin Packing with Conflicts
    Huang, Zhihua
    Zhang, An
    Dosa, Gyorgy
    Chen, Yong
    Xiong, Chenling
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2023,
  • [39] Techniques and results on approximation algorithms for packing circles
    Flávio K. Miyazawa
    Yoshiko Wakabayashi
    São Paulo Journal of Mathematical Sciences, 2022, 16 : 585 - 615
  • [40] A NEW APPROXIMATION METHOD FOR SET COVERING PROBLEMS, WITH APPLICATIONS TO MULTIDIMENSIONAL BIN PACKING
    Bansal, Nikhil
    Caprara, Alberto
    Sviridenko, Maxim
    SIAM JOURNAL ON COMPUTING, 2009, 39 (04) : 1256 - 1278
12345