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 条
  • [41] Randomized approximation of bounded multicovering problems
    D. Peleg
    G. Schechtman
    A. Wool
    Algorithmica, 1997, 18 : 44 - 66
  • [42] Randomized approximation of bounded multicovering problems
    Peleg, D
    Schechtman, G
    Wool, A
    ALGORITHMICA, 1997, 18 (01) : 44 - 66
  • [43] Peak Demand Minimization via Sliced Strip Packing
    Deppert, Max A.
    Jansen, Klaus
    Khan, Arindam
    Rau, Malin
    Tutas, Malte
    ALGORITHMICA, 2023, 85 (12) : 3649 - 3679
  • [44] A Tabu Search Algorithm with Direct Representation for Strip Packing
    Hamiez, Jean-Philippe
    Robet, Julien
    Hao, Jin-Kao
    EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, PROCEEDINGS, 2009, 5482 : 61 - 72
  • [45] A Hyper-Heuristic Approach to Strip Packing Problems
    Burke, Edmund K.
    Guo, Qiang
    Kendall, Graham
    PARALLEL PROBLEMS SOLVING FROM NATURE - PPSN XI, PT I, 2010, 6238 : 465 - 474
  • [46] An evolutionary hyperheuristic to solve strip-packing problems
    Garrido, Pablo
    Riff, Maria-Cristina
    INTELLIGENT DATA ENGINEERING AND AUTOMATED LEARNING - IDEAL 2007, 2007, 4881 : 406 - 415
  • [47] Probabilistic Analysis of a New Class of Strip Packing Algorithms
    Kuzyurin, N. N.
    Pospelov, A. I.
    COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS, 2011, 51 (10) : 1817 - 1822
  • [48] Resolution of strip-packing problems with genetic algorithms
    Gómez, A
    de la Fuente, D
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2000, 51 (11) : 1289 - 1295
  • [49] Heuristic for the rectangular strip packing problem with rotation of items
    Cui, Yaodong
    Yang, Liu
    Chen, Qiulian
    COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (04) : 1094 - 1099
  • [50] Two-dimensional strip packing with unloading constraints
    da Silveira, Jefferson L. M.
    Xavier, Eduardo C.
    Miyazawa, Flavio K.
    DISCRETE APPLIED MATHEMATICS, 2014, 164 : 512 - 521
12345