A note on online strip packing

被引：28

作者：

Ye, Deshi ^{[2
]}

Han, Xin ^{[3
]}

Zhang, Guochuan ^{[1
]}

机构：

[1] Zhejiang Univ, Dept Math, Hangzhou 310027, Peoples R China

[2] Zhejiang Univ, Coll Comp Sci, Hangzhou 310027, Peoples R China

[3] Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2009年 / 17卷 / 04期

关键词：

Strip packing; Online algorithms; Competitive ratio; PARALLEL JOBS; ALGORITHMS; BOUNDS;

D O I：

10.1007/s10878-007-9125-x

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In online strip packing we are asked to pack a list of rectangles one by one into a vertical strip of unit width, without any information about future rectangles. The goal is to minimize the total height of strip used. The best known algorithm is First Fit Shelf algorithm (Baker and Schwarz in SIAM J. Comput. 12(3): 508-525, 1983), which has an absolute competitive ratio of 6.99 under the assumption that the height of each rectangle is bounded from above by one. We improve the shelf algorithm and show an absolute competitive ratio of 7/2 + root 10 approximate to 6.6623 without the restriction on rectangle heights. Our algorithm also beats the best known online algorithm for parallel job scheduling.

引用

页码：417 / 423

页数：7

共 20 条

[1]

[Anonymous], 1998, Online Computation and Competitive Analysis

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

BAKER, BS ;

COFFMAN, EG ;

RIVEST, RL .

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

[3] SHELF ALGORITHMS FOR TWO-DIMENSIONAL PACKING PROBLEMS [J].

BAKER, BS ;

SCHWARZ, JS .

SIAM JOURNAL ON COMPUTING, 1983, 12 (03) :508-525

[4]

BROWN DJ, 1982, ACTA INFORM, V18, P207, DOI 10.1007/BF00264439

[5]

CHAN WT, 2007, J DISCRETE IN PRESS

[6]

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

[7] Algorithms for on-line strip packing [J].

Csirik, J ;

Woeginger, GJ .

INFORMATION PROCESSING LETTERS, 1997, 63 (04) :171-175

[8]

Csirik J, 1998, LECT NOTES COMPUT SC, V1442, P147, DOI 10.1007/BFb0029568

[9]

Drozdowski M., 2004, HDB SCHEDULING ALGOR

[10]

Du J., 1989, SIAM Journal on Discrete Mathematics, V2, P473, DOI [10.1137/0402042, DOI 10.1137/0402042]

← 1 2 →