Online algorithms for 1-space bounded 2-dimensional bin packing and square packing

Yong Zhang; Francis Y.L. Chin; Hing-Fung Ting; Xin Han; Chung Keung Poon; Yung H. Tsin; Deshi Ye

doi:10.1016/j.tcs.2014.02.045

Online algorithms for 1-space bounded 2-dimensional bin packing and square packing

Yong Zhang
, Francis Y.L. Chin
, Hing-Fung Ting
, Xin Han
, Chung Keung Poon
, Yung H. Tsin
, Deshi Ye

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

8 Citations (Scopus)

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°-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. © 2014 Elsevier B.V.

Original language	English
Pages (from-to)	135-149
Journal	Theoretical Computer Science
Volume	554
Issue number	C
DOIs	https://doi.org/10.1016/j.tcs.2014.02.045
Publication status	Published - 2014

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

1 Research supported by NSFC 11171086 and Natural Science Foundation of Hebei Province A2013201218. 2 Research supported by HK RGC grant HKU-711709E. 3 Research supported by HK RGC grant HKU-716412E. 4 Partially supported by “the Fundamental Research Funds for the Central Universities (DUT12LK09)” and NSFC 11101065. 5 Research supported by NSERC under grant NSERC 7811-2009. 6 Research supported by NSFC 11071215.

Research Keywords

Competitive analysis
Square packing
Two dimensional bin packing

RGC Funding Information

RGC-funded

Access Output

10.1016/j.tcs.2014.02.045Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{e2bd0f0c64c24313885f1f30be3961c8,

title = "Online algorithms for 1-space bounded 2-dimensional bin packing and 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°-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. {\textcopyright} 2014 Elsevier B.V.",

keywords = "Competitive analysis, Square packing, Two dimensional bin packing",

author = "Yong Zhang and Chin, \{Francis Y.L.\} and Hing-Fung Ting and Xin Han and Poon, \{Chung Keung\} and Tsin, \{Yung H.\} and Deshi Ye",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2014",

doi = "10.1016/j.tcs.2014.02.045",

language = "English",

volume = "554",

pages = "135--149",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "C",

}

TY - JOUR

T1 - Online algorithms for 1-space bounded 2-dimensional bin packing and square packing

AU - Zhang, Yong

AU - Chin, Francis Y.L.

AU - Ting, Hing-Fung

AU - Han, Xin

AU - Poon, Chung Keung

AU - Tsin, Yung H.

AU - Ye, Deshi

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2014

Y1 - 2014

N2 - 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°-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. © 2014 Elsevier B.V.

AB - 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°-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. © 2014 Elsevier B.V.

KW - Competitive analysis

KW - Square packing

KW - Two dimensional bin packing

UR - https://www.scopus.com/pages/publications/84921535358

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84921535358&origin=recordpage

U2 - 10.1016/j.tcs.2014.02.045

DO - 10.1016/j.tcs.2014.02.045

M3 - RGC 21 - Publication in refereed journal

SN - 0304-3975

VL - 554

SP - 135

EP - 149

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -

Online algorithms for 1-space bounded 2-dimensional bin packing and square packing

Abstract

Bibliographical note

Funding

Research Keywords

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this