.png){kind=icon}
返回
Parametric on-line algorithms for packing rectangles and boxes
.png){kind=icon}
PRE
AI
DOI：10.1016/S0377-2217(02)00539-8.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We present approximation algorithms for the following problems: the two-dimensional bin packing (2BP), the three-dimensional packing problem (TPP) and the container packing problem (3BP). We consider the special case in which the items to be packed are small and must be packed on-line. We say an item is small if each of its dimension is at most 1/M of the respective dimension of the recipient, where m is an integer greater than 1. These problems are denoted by 2BP(m), TPPm and 3BP(m), and the performance of the algorithms are given in terms of the parameter m. To our knowledge, the parametric on-line algorithms we present here have the best so far achieved asymptotic performance bounds for these problems. For 2BP, and TPP we present algorithms with performance bound close to (m + 2)/m + 1/(m + 1)(2), and for 3BP(m) we describe an algorithm with performance bound close to (m + 3)/m + 2/m(2) + 1/(m + 1)(2). For m = 2 (respectively m = 3) these bounds are 2.112 and 3.112 (respectively 1.73 and 2.285). The results on 2BP(m) and 3BP(m) extend the results on multidimensional on-line packing presented by Coppersmith and Raghavan [Oper. Res. Lett. 8(l) (1989) 17]. The result on TPPm improves the bound (m + 1)/(m - 1) due to Li and Cheng [SIAM J. Comput. 19 (1990) 847]. All these algorithms can be implemented to run in O(n log n) time, where n is the number of items to be packed. (C) 2002 Elsevier Science B.V. All rights reserved.
Keyword:
packing
On-line packing
parametric packing
approximation algorithms
three-dimensional packing
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
暂无机构信息
引用论文
Bioactive ingredients and microbial diversity of Fuzhuan tea produced from different raw materials.茯砖茶中活性成分及由不同原料生产的微生物多样性。.png)
IF0
PREAI
分享收藏
查看更多内容