File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: 1-bounded space algorithms for 2-dimensional bin packing

Title1-bounded space algorithms for 2-dimensional bin packing
Authors
Issue Date2009
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
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 How to Cite?
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
Persistent Identifierhttp://hdl.handle.net/10722/151965
ISBN
ISSN
2014 SCImago Journal Rankings: 0.339
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_US
dc.contributor.authorTing, HFen_US
dc.contributor.authorZhang, Yen_US
dc.date.accessioned2012-06-26T06:31:37Z-
dc.date.available2012-06-26T06:31:37Z-
dc.date.issued2009en_US
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-330en_US
dc.identifier.isbn978-3-642-10630-9-
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/151965-
dc.descriptionLNCS v. 5878 entitled: Algorithms and Computation : 20th International Symposium, ISAAC 2009 ... proceedings-
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.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.title1-bounded space algorithms for 2-dimensional bin packingen_US
dc.typeConference_Paperen_US
dc.identifier.emailChin, FYL: chin@cs.hku.hken_US
dc.identifier.emailTing, HF: hfting@cs.hku.hken_US
dc.identifier.emailZhang, Y: yzhang@cs.hku.hk-
dc.identifier.authorityTing, HF=rp00177en_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/978-3-642-10631-6_34en_US
dc.identifier.scopuseid_2-s2.0-75649136236en_US
dc.identifier.hkuros166458-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-75649136236&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume5878en_US
dc.identifier.spage321en_US
dc.identifier.epage330en_US
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridZhang, Y=7601329213en_US
dc.identifier.scopusauthoridTing, HF=7005654198en_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.customcontrol.immutablesml 140807-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats