Conference Paper: 1-bounded space algorithms for 2-dimensional bin packing
| Title | 1-bounded space algorithms for 2-dimensional bin packing |
|---|---|
| Authors | Chin, FYL1 Ting, HF1 Zhang, Y1 |
| Issue Date | 2009 |
| Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| Citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5878 LNCS, p. 321-330 [How to Cite?] DOI: http://dx.doi.org/10.1007/978-3-642-10631-6_34 |
| Abstract | In this paper, we study the bounded space variation, especially 1-bounded space, of 2-dimensional bin packing. A sequence of rectangular items arrive over time, and the following item arrives after the packing of the previous one. The height and width of each item are no more than 1, we need to pack these items into unit square bins of size 1×1 and our objective is to minimize the number of used bins. Once an item is packed into a square bin, the position of this item is fixed and it cannot be shifted within this bin. At any time, there is at most one active bin; the current unpacked item can be only packed into the active bin and the inactive bins (closed at some previous time) cannot be used for any future items. We first propose an online algorithm with a constant competitive ratio 12, then improve the competitive ratio to 8.84 by the some complicated analysis. Our results significantly improve the previous best known O((loglogm)2)-competitive algorithm[10], where m is the width of the square bin and the size of each item is a×b, where a, b are integers no more than m. Furthermore, the lower bound for the competitive ratio is also improved to 2.5. © 2009 Springer-Verlag Berlin Heidelberg. |
| ISSN | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| DOI | http://dx.doi.org/10.1007/978-3-642-10631-6_34 |
| References | References in Scopus |
| dc.contributor.author | Chin, FYL |
|---|---|
| dc.contributor.author | Ting, HF |
| dc.contributor.author | Zhang, Y |
| dc.date.accessioned | 2012-06-26T06:31:37Z |
| dc.date.available | 2012-06-26T06:31:37Z |
| dc.date.issued | 2009 |
| dc.description.abstract | In this paper, we study the bounded space variation, especially 1-bounded space, of 2-dimensional bin packing. A sequence of rectangular items arrive over time, and the following item arrives after the packing of the previous one. The height and width of each item are no more than 1, we need to pack these items into unit square bins of size 1×1 and our objective is to minimize the number of used bins. Once an item is packed into a square bin, the position of this item is fixed and it cannot be shifted within this bin. At any time, there is at most one active bin; the current unpacked item can be only packed into the active bin and the inactive bins (closed at some previous time) cannot be used for any future items. We first propose an online algorithm with a constant competitive ratio 12, then improve the competitive ratio to 8.84 by the some complicated analysis. Our results significantly improve the previous best known O((loglogm)2)-competitive algorithm[10], where m is the width of the square bin and the size of each item is a×b, where a, b are integers no more than m. Furthermore, the lower bound for the competitive ratio is also improved to 2.5. © 2009 Springer-Verlag Berlin Heidelberg. |
| dc.description.nature | Link_to_subscribed_fulltext |
| dc.identifier.citation | Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5878 LNCS, p. 321-330 [How to Cite?] DOI: http://dx.doi.org/10.1007/978-3-642-10631-6_34 |
| dc.identifier.doi | http://dx.doi.org/10.1007/978-3-642-10631-6_34 |
| dc.identifier.epage | 330 |
| dc.identifier.issn | 0302-9743 2011 SCImago Journal Rankings: 0.034 |
| dc.identifier.scopus | eid_2-s2.0-75649136236 |
| dc.identifier.spage | 321 |
| dc.identifier.uri | http://hdl.handle.net/10722/151965 |
| dc.identifier.volume | 5878 LNCS |
| dc.language | eng |
| dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
| dc.publisher.place | Germany |
| dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| dc.relation.references | References in Scopus |
| dc.title | 1-bounded space algorithms for 2-dimensional bin packing |
| dc.type | Conference_Paper |
Author Affiliations
- The University of Hong Kong