点击次数：

论文类型：期刊论文

发表时间：2014-10-16

发表刊物：19th Annual International Computing and Combinatorics Conference (COCOON)

收录刊物：SCIE、EI、CPCI-S、Scopus

卷号：554

期号：C

页面范围：135-149

ISSN号：0304-3975

关键字：Competitive analysis; Two dimensional bin packing; Square packing

摘要：In this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items) arrive one by one, each item must be packed into a square bin of unit size on its arrival without any information about future items. When packing items, 90 degrees-rotation is allowed. 1-space bounded means there is only one "active" bin. If the "active" bin cannot accommodate the coming item, it will be closed and a new bin will be opened. The objective is to minimize the total number of bins used for packing all items in the sequence.
   Our contributions are as follows: For 1-space bounded 2-dimensional bin packing, we propose an online packing algorithm with a tight competitive ratio of 5.06. A lower bound of 3.17 on the competitive ratio is proven. Moreover, we study 1-space bounded square packing, where each item is a square with side length no more than 1. A 4.3-competitive algorithm is achieved, and a lower bound of 2.94 on the competitive ratio is given. All these bounds surpass the previously best known results. (C) 2014 Elsevier B.V. All rights reserved.