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 条
  • [1] Improved approximation for two dimensional Strip Packing with polynomial bounded width
    Jansen, Klaus
    Rau, Malin
    THEORETICAL COMPUTER SCIENCE, 2019, 789 : 34 - 49
  • [2] Improved Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width
    Jansen, Klaus
    Rau, Malin
    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, 2017, 10167 : 409 - 420
  • [3] Approximation Algorithms for Multiple Strip Packing
    Bougeret, Marin
    Dutot, Pierre Francois
    Jansen, Klaus
    Otte, Christina
    Trystram, Denis
    APPROXIMATION AND ONLINE ALGORITHMS, 2010, 5893 : 37 - +
  • [4] A Tight (3/2+ε)-Approximation for Skewed Strip Packing
    Galvez, Waldo
    Grandoni, Fabrizio
    Ameli, Afrouz Jabal
    Jansen, Klaus
    Khan, Arindam
    Rau, Malin
    ALGORITHMICA, 2023, 85 (10) : 3088 - 3109
  • [5] A (5/3+ε)-Approximation for Strip Packing
    Harren, Rolf
    Jansen, Klaus
    Praedel, Lars
    van Stee, Rob
    ALGORITHMS AND DATA STRUCTURES, 2011, 6844 : 475 - +
  • [6] A (5/3+ε)-approximation for strip packing
    Harren, Rolf
    Jansen, Klaus
    Praedel, Lars
    van Stee, Rob
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2014, 47 (02): : 248 - 267
  • [7] A New Asymptotic Approximation Algorithm for 3-Dimensional Strip Packing
    Jansen, Klaus
    Praedel, Lars
    SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2014, 8327 : 327 - 338
  • [8] Strip packing with precedence constraints and strip packing with release times
    Augustine, John
    Banerjee, Sudarshan
    Irani, Sandy
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) : 3792 - 3803
  • [9] Bin packing in multiple dimensions: Inapproximability results and approximation schemes
    Bansal, N
    Correa, JR
    Kenyon, C
    Sviridenko, M
    MATHEMATICS OF OPERATIONS RESEARCH, 2006, 31 (01) : 31 - 49
  • [10] Chips on wafers, or packing rectangles into grids
    Andersson, M
    Gudmundsson, J
    Levcopoulos, C
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2005, 30 (02): : 95 - 111
12345