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 条
  • [21] A new upper bound for the online square packing problem in a strip
    Yu, Guosong
    Mao, Yanling
    Xiao, Jiaoliao
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (04) : 1411 - 1420
  • [22] New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems
    Ortmann, Frank G.
    Ntene, Nthabiseng
    van Vuuren, Jan H.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 203 (02) : 306 - 315
  • [23] Online multiple-strip packing
    Ye, Deshi
    Han, Xin
    Zhang, Guochuan
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (03) : 233 - 239
  • [24] A 3-approximation algorithm for two-dimensional bin packing
    Zhang, GC
    OPERATIONS RESEARCH LETTERS, 2005, 33 (02) : 121 - 126
  • [25] On-Line Multiple-Strip Packing
    Ye, Deshi
    Han, Xin
    Zhang, Guochuan
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2009, 5573 : 155 - +
  • [26] A new lower bound for online strip packing
    Yu, Guosong
    Mao, Yanling
    Xiao, Jiaoliao
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 250 (03) : 754 - 759
  • [27] Improved Lower Bound for Online Strip Packing
    Rolf Harren
    Walter Kern
    Theory of Computing Systems, 2015, 56 : 41 - 72
  • [28] Heuristics for the strip packing problem with unloading constraints
    da Silveira, Jefferson L. M.
    Miyazawa, Flavio K.
    Xavier, Eduardo C.
    COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (04) : 991 - 1003
  • [29] Hardness and Tight Approximations of Demand Strip Packing
    Jansen, Klaus
    Rau, Malin
    Tutas, Malte
    PROCEEDINGS OF THE 36TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2024, 2024, : 479 - 489
  • [30] New upper bounds for online strip packing
    Yu, Guosong
    Mao, Yanling
    Xiao, Jiaoliao
    DISCRETE OPTIMIZATION, 2017, 23 : 20 - 32
12345