Indexed by:Journal Article

Date of Publication:2014-10-16

Journal:19th Annual International Computing and Combinatorics Conference (COCOON)

Included Journals:Scopus、CPCI-S、EI、SCIE

Volume:554

Issue:C

Page Number:135-149

ISSN:0304-3975

Key Words:Competitive analysis; Two dimensional bin packing; Square packing

Abstract: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.