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

共 10 条

[1] ORTHOGONAL PACKINGS IN 2 DIMENSIONS [J].

BAKER, BS ;

COFFMAN, EG ;

RIVEST, RL .

SIAM JOURNAL ON COMPUTING, 1980, 9 (04) :846-855

[2] A 5-4 ALGORITHM FOR TWO-DIMENSIONAL PACKING [J].

BAKER, BS ;

BROWN, DJ ;

KATSEFF, HP .

JOURNAL OF ALGORITHMS, 1981, 2 (04) :348-368

[3]

Blum M., 1973, Journal of Computer and System Sciences, V7, P448, DOI 10.1016/S0022-0000(73)80033-9

[4]

COFFMAN EG, 1980, SIAM J COMPUT, V9, P808, DOI 10.1137/0209062

[5]

DELAVEGA WF, 1981, COMBINATORICA, V1, P349

[6]

GOLAN I, 1978, ORTHOGONAL ORIENTED

[7] THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE [J].

JOHNSON, DS .

JOURNAL OF ALGORITHMS, 1982, 3 (03) :288-300

[8]

Karmarkar N., 1982, 23rd Annual Symposium on Foundations of Computer Science, P312, DOI 10.1109/SFCS.1982.61

[9]

KENYON C, 1996, 37 S FDN COMP SCI

[10] INTEGER PROGRAMMING WITH A FIXED NUMBER OF VARIABLES [J].

LENSTRA, HW .

MATHEMATICS OF OPERATIONS RESEARCH, 1983, 8 (04) :538-548

← 1 →