File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: 1-bounded space algorithms for 2-dimensional bin packing
  • Basic View
  • Metadata View
  • XML View
Title1-bounded space algorithms for 2-dimensional bin packing
 
AuthorsChin, FYL1
Ting, HF1
Zhang, Y1
 
Issue Date2009
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
CitationThe 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, HI., 16-18 December 2009. In Lecture Notes in Computer Science, 2009, v. 5878, p. 321-330 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-10631-6_34
 
AbstractIn 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.
 
DescriptionLNCS v. 5878 entitled: Algorithms and Computation : 20th International Symposium, ISAAC 2009 ... proceedings
 
ISBN978-3-642-10630-9
 
ISSN0302-9743
2013 SCImago Journal Rankings: 0.310
 
DOIhttp://dx.doi.org/10.1007/978-3-642-10631-6_34
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorChin, FYL
 
dc.contributor.authorTing, HF
 
dc.contributor.authorZhang, Y
 
dc.date.accessioned2012-06-26T06:31:37Z
 
dc.date.available2012-06-26T06:31:37Z
 
dc.date.issued2009
 
dc.description.abstractIn 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.naturelink_to_subscribed_fulltext
 
dc.descriptionLNCS v. 5878 entitled: Algorithms and Computation : 20th International Symposium, ISAAC 2009 ... proceedings
 
dc.identifier.citationThe 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, HI., 16-18 December 2009. In Lecture Notes in Computer Science, 2009, v. 5878, p. 321-330 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-10631-6_34
 
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-10631-6_34
 
dc.identifier.epage330
 
dc.identifier.hkuros166458
 
dc.identifier.isbn978-3-642-10630-9
 
dc.identifier.issn0302-9743
2013 SCImago Journal Rankings: 0.310
 
dc.identifier.scopuseid_2-s2.0-75649136236
 
dc.identifier.spage321
 
dc.identifier.urihttp://hdl.handle.net/10722/151965
 
dc.identifier.volume5878
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science
 
dc.relation.referencesReferences in Scopus
 
dc.rightsThe original publication is available at www.springerlink.com
 
dc.title1-bounded space algorithms for 2-dimensional bin packing
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Chin, FYL</contributor.author>
<contributor.author>Ting, HF</contributor.author>
<contributor.author>Zhang, Y</contributor.author>
<date.accessioned>2012-06-26T06:31:37Z</date.accessioned>
<date.available>2012-06-26T06:31:37Z</date.available>
<date.issued>2009</date.issued>
<identifier.citation>The 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, HI., 16-18 December 2009. In Lecture Notes in Computer Science, 2009, v. 5878, p. 321-330</identifier.citation>
<identifier.isbn>978-3-642-10630-9</identifier.isbn>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/151965</identifier.uri>
<description>LNCS v. 5878 entitled: Algorithms and Computation : 20th International Symposium, ISAAC 2009 ... proceedings</description>
<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&#215;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&#215;b, where a, b are integers no more than m. Furthermore, the lower bound for the competitive ratio is also improved to 2.5. &#169; 2009 Springer-Verlag Berlin Heidelberg.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science</relation.ispartof>
<rights>The original publication is available at www.springerlink.com</rights>
<title>1-bounded space algorithms for 2-dimensional bin packing</title>
<type>Conference_Paper</type>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1007/978-3-642-10631-6_34</identifier.doi>
<identifier.scopus>eid_2-s2.0-75649136236</identifier.scopus>
<identifier.hkuros>166458</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-75649136236&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>5878</identifier.volume>
<identifier.spage>321</identifier.spage>
<identifier.epage>330</identifier.epage>
<publisher.place>Germany</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong