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 条
  • [21] Parameterized complexity of Strip Packing and Minimum Volume Packing
    Ashok, Pradeesha
    Kolay, Sudeshna
    Meesum, S. M.
    Saurabh, Saket
    THEORETICAL COMPUTER SCIENCE, 2017, 661 : 56 - 64
  • [22] A note on online strip packing
    Ye, Deshi
    Han, Xin
    Zhang, Guochuan
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 17 (04) : 417 - 423
  • [23] A note on online strip packing
    Deshi Ye
    Xin Han
    Guochuan Zhang
    Journal of Combinatorial Optimization, 2009, 17 : 417 - 423
  • [24] Closing the Gap for Pseudo-Polynomial Strip Packing
    Jansen, Klaus
    Rau, Malin
    27TH ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS (ESA 2019), 2019, 144
  • [25] A note on the Kenyon-Remila strip-packing algorithm
    Sviridenko, Maxim
    INFORMATION PROCESSING LETTERS, 2012, 112 (1-2) : 10 - 12
  • [26] Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing
    Henning, Soeren
    Jansen, Klaus
    Rau, Malin
    Schmarje, Lars
    THEORY OF COMPUTING SYSTEMS, 2020, 64 (01) : 120 - 140
  • [27] A HARMONIC ALGORITHM FOR THE 3D STRIP PACKING PROBLEM
    Bansal, Nikhil
    Han, Xin
    Iwama, Kazuo
    Sviridenko, Maxim
    Zhang, Guochuan
    SIAM JOURNAL ON COMPUTING, 2013, 42 (02) : 579 - 592
  • [28] Algorithms for on-line strip packing
    Csirik, J
    Woeginger, GJ
    INFORMATION PROCESSING LETTERS, 1997, 63 (04) : 171 - 175
  • [29] Online strip packing with modifiable boxes
    Imreh, C
    OPERATIONS RESEARCH LETTERS, 2001, 29 (02) : 79 - 85
  • [30] Partitioning a square into rectangles: NP-completeness and approximation algorithms
    Beaumont, O
    Boudet, V
    Rastello, F
    Robert, Y
    ALGORITHMICA, 2002, 34 (03) : 217 - 239
12345