An approximation scheme for strip packing of rectangles with bounded dimensions

被引：10
|
作者：
de la Vega, WF [1 ]
Zissimopoulos, V [1 ]
机构：
[1] Univ Paris 11, LRI, CNRS, URA 410, F-91405 Orsay, France
来源：
DISCRETE APPLIED MATHEMATICS | 1998年 / 82卷 / 1-3期
关键词：
strip packing; approximation algorithms;
D O I：
10.1016/S0166-218X(97)00130-3
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
It is shown that for any positive epsilon the strip-packing problem, i.e. the problem of packing a given list of rectangles into a strip of width 1 and minimum height, can be solved within 1 + epsilon times the optimal height, in linear time, if the heights and widths of these rectangles are all bounded below by an absolute constant delta > 0. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：93 / 101
页数：9
相关论文
共 50 条
  • [31] The variable-width strip packing problem
    Bodis, Attila
    Csirik, Janos
    CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2022, 30 (04) : 1337 - 1351
  • [32] Improved Lower Bound for Online Strip Packing
    Harren, Rolf
    Kern, Walter
    THEORY OF COMPUTING SYSTEMS, 2015, 56 (01) : 41 - 72
  • [33] A branch and bound algorithm for the strip packing problem
    Alvarez-Valdes, R.
    Parreno, F.
    Tamarit, J. M.
    OR SPECTRUM, 2009, 31 (02) : 431 - 459
  • [34] A new lower bound for online strip packing
    Yu, Guosong
    Mao, Yanling
    Xiao, Jiaoliao
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 250 (03) : 754 - 759
  • [35] Reactive GRASP for the strip-packing problem
    Alvarez-Valdes, R.
    Parreno, F.
    Tamarit, J. M.
    COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (04) : 1065 - 1083
  • [36] A branch and bound algorithm for the strip packing problem
    R. Alvarez-Valdes
    F. Parreño
    J. M. Tamarit
    OR Spectrum, 2009, 31 : 431 - 459
  • [37] Improved Lower Bound for Online Strip Packing
    Rolf Harren
    Walter Kern
    Theory of Computing Systems, 2015, 56 : 41 - 72
  • [38] New upper bounds for online strip packing
    Yu, Guosong
    Mao, Yanling
    Xiao, Jiaoliao
    DISCRETE OPTIMIZATION, 2017, 23 : 20 - 32
  • [39] The variable-width strip packing problem
    Attila Bódis
    János Csirik
    Central European Journal of Operations Research, 2022, 30 : 1337 - 1351
  • [40] An -Approximation for Covering and Packing Minor Models of
    Chatzidimitriou, Dimitris
    Raymond, Jean-Florent
    Sau, Ignasi
    Thilikos, Dimitrios M.
    ALGORITHMICA, 2018, 80 (04) : 1330 - 1356
12345