Resource augmentation in two-dimensional packing with orthogonal rotations

被引：10

作者：

Correa, JR ^{[1
]}

机构：

[1] Univ Adolfo Ibanez, Sch Business, Santiago, Chile

来源：

OPERATIONS RESEARCH LETTERS | 2006年 / 34卷 / 01期

关键词：

bin packing; approximation algorithms; polynomial time approximation schemes;

D O I：

10.1016/j.orl.2005.02.005

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90 degrees rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1 + epsilon), for any positive e. Additionally, we show near-optimal packing results for a number of related packing problems. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：85 / 93

页数：9

共 16 条

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

BAKER, BS ;

BROWN, DJ ;

KATSEFF, HP .

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

[2]

BANSAL N, 2004, P 15 ANN ACM SIAM S, P189

[3]

BANSAL N, 2004, BIN PACKING MULT NOV

[4]

Caprara A, 2002, ANN IEEE SYMP FOUND, P490, DOI 10.1109/SFCS.2002.1181973

[5]

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

[6]

CORREA JR, 2004, P 15 ACM SIAM S DISC, P179

[7]

EPSTEIN L, 2004, IN PRESS P 2 WORKSH

[8]

Ferreira C.E., 1999, PESQUISA OPERATIONAL, V19, P223

[9] A near-optimal solution to a two-dimensional cutting stock problem [J].

Kenyon, C ;

Rémila, E .

MATHEMATICS OF OPERATIONS RESEARCH, 2000, 25 (04) :645-656

[10]

KENYON C, 2003, COMMUNICATION OCT

← 1 2 →