Paper Info
Title
Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing
Abstract
In this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items, respectively) arrive over time, which must be packed into square bins of size 1 x 1. 90 degrees-rotation of an item is allowed. When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items. The objective is to minimize the total number of bins used for packing all the items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened. Our contributions are as follows: For 1-space bounded 2-dimensional bin packing, we propose an online packing strategy with competitive ratio 5.155, surpassing the previous 8.84-competitive bound. The lower bound of competitive ratio is also improved from 2.5 to 3. Furthermore, we study 1-space bounded square packing, which is a special case of the bin packing problem. We give a 4.5-competitive packing algorithm, and prove that the lower bound of competitive ratio is at least 8/3.
Year
DOI
Venue
2010
10.1007/978-3-642-17514-5_21
ALGORITHMS AND COMPUTATION, PT 2
Keywords
Field
DocType
competitive ratio,bin packing problem,online algorithm,lower bound,2 dimensional,bin packing
Discrete mathematics,Online algorithm,Combinatorics,Bin,Square packing in a square,Mathematics,Bin packing problem,Competitive analysis,Bounded function
Conference
Volume
ISSN
Citations 
6507
0302-9743
11
PageRank 
References 
Authors
0.71
17
6
Name
Order
Citations
PageRank
Yong Zhang16810.51
Jing-Chi Chen2453.08
Francis Y. L. Chin32173377.15
Xin Han421324.49
Hing-Fung Ting5396.74
Yung H. Tsin615921.99