Online algorithms for 2D bin packing with advice

NEUROCOMPUTING

卷:189

Article

Zhao, Xiaofan^1,2  Shen, Hong^1,3,4 

[1] Beijing Jiaotong Univ, Sch Comp & Informat Technol, Beijing, Peoples R China

[2] Zhengzhou Univ, Affiliated Hosp 5, Dept Informat, Zhengzhou 450052, Peoples R China

[3] Sun Yat Sen Univ, Sch Informat Sci & Technol, Guangzhou 510275, Guangdong, Peoples R China

[4] Univ Adelaide, Sch Comp Sci, Adelaide, SA 5005, Australia

关键词: Online 2D packing;    Rotatable;    Advice string;    Asymptotic worst case ratio;   

DOI  :  10.1016/j.neucom.2015.11.035

来源: Elsevier

【 摘 要 】

In advice complexity model of online bin packing, suppose there is an offline oracle with infinite computational power. The oracle can provide some information to the online calculation about future items after scanning the whole list of items. This approach can loosen online constraints. The online algorithm receives an advice bit upon the arrival of each item and makes the packing decision. In 2-dimensional online bin packing with advice problem, each item is a rectangle of side lengths less than or equal to 1. The items are to be packed into square bins of size 1 x 1, without overlapping, allowing 90 degrees rotations. The goal is to pack the items into the minimum number of square bins. In this paper, a 2.25-competitive 2-dimensional online rectangular packing algorithm with three bits of advice per item is presented. Furthermore, an online strategy with competitive ratio 2 requiring three bits of advice per item is given for square packing. (C) 2016 Published by Elsevier B.V.

【 授权许可】

Free