Probabilistic analysis of shelf algorithms for strip packing

被引：0
作者：
Kuzyurin, N. N.
Pospelov, A. I.
机构：
来源：
DISCRETE MATHEMATICS AND APPLICATIONS | 2006年 / 16卷 / 01期
关键词：
D O I：
10.1163/156939206776241228
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we consider algorithms to pack rectangles into a strip. As the main result we present an algorithm that packs rectangles online and for which the ratio of expected wasted area to expected occupied area tends to zero as the number of rectangles increases. The research was supported by the Russian Foundation for Basic Research, grants 05-01-00798 and 04-01-00359.
引用
收藏
页码：61 / 72
页数：12
相关论文
共 12 条
[1]  
[Anonymous], 1998, SCHEDULING ALGORITHM
[2]   ORTHOGONAL PACKINGS IN 2 DIMENSIONS [J].
BAKER, BS ;
COFFMAN, EG ;
RIVEST, RL .
SIAM JOURNAL ON COMPUTING, 1980, 9 (04) :846-855
[3]   A 5-4 ALGORITHM FOR TWO-DIMENSIONAL PACKING [J].
BAKER, BS ;
BROWN, DJ ;
KATSEFF, HP .
JOURNAL OF ALGORITHMS, 1981, 2 (04) :348-368
[4]   SHELF ALGORITHMS FOR TWO-DIMENSIONAL PACKING PROBLEMS [J].
BAKER, BS ;
SCHWARZ, JS .
SIAM JOURNAL ON COMPUTING, 1983, 12 (03) :508-525
[5]  
Coffman E. G., 1984, APPROXIMATION ALGORI, P49, DOI DOI 10.1007/978-3-7091-4338-4
[6]   Perfect packing theorems and the average-case behavior of optimal and online bin packing [J].
Coffman, EG ;
Courcoubetis, C ;
Garey, MR ;
Johnson, DS ;
Shor, PW ;
Weber, RR ;
Yannakakis, M .
SIAM REVIEW, 2002, 44 (01) :95-108
[7]  
COFFMAN EG, 1980, SIAM J COMPUT, V9, P808, DOI 10.1137/0209062
[8]  
Csirik J., 2000, Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, P208, DOI 10.1145/335305.335331
[9]  
Karp R. M., 1984, P 16 ANN ACM S THEOR, P289
[10]   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
12