File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: One-space bounded algorithms for two-dimensional bin packing

TitleOne-space bounded algorithms for two-dimensional bin packing
Authors
Keywordsbin packing
bounded space
competitive analysis
Online algorithms
Issue Date2010
PublisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijfcs/ijfcs.shtml
Citation
International Journal Of Foundations Of Computer Science, 2010, v. 21 n. 6, p. 875-891 How to Cite?
AbstractIn this paper, we study the bounded space variation, especially one-space bounded, of two-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 where rotation of 90° is allowed 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((log log m) 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. © 2010 World Scientific Publishing Company.
Persistent Identifierhttp://hdl.handle.net/10722/140805
ISSN
2015 Impact Factor: 0.467
2015 SCImago Journal Rankings: 0.394
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorZhang, Yen_HK
dc.date.accessioned2011-09-23T06:19:32Z-
dc.date.available2011-09-23T06:19:32Z-
dc.date.issued2010en_HK
dc.identifier.citationInternational Journal Of Foundations Of Computer Science, 2010, v. 21 n. 6, p. 875-891en_HK
dc.identifier.issn0129-0541en_HK
dc.identifier.urihttp://hdl.handle.net/10722/140805-
dc.description.abstractIn this paper, we study the bounded space variation, especially one-space bounded, of two-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 where rotation of 90° is allowed 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((log log m) 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. © 2010 World Scientific Publishing Company.en_HK
dc.languageengen_US
dc.publisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijfcs/ijfcs.shtmlen_HK
dc.relation.ispartofInternational Journal of Foundations of Computer Scienceen_HK
dc.rightsInternational Journal of Foundations of Computer Science. Copyright © World Scientific Publishing Co Pte Ltd.-
dc.subjectbin packingen_HK
dc.subjectbounded spaceen_HK
dc.subjectcompetitive analysisen_HK
dc.subjectOnline algorithmsen_HK
dc.titleOne-space bounded algorithms for two-dimensional bin packingen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0129-0541&volume=21&issue=6&spage=875&epage=891&date=2010&atitle=One-space+bounded+algorithms+for+two-dimensional+bin+packing-
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1142/S0129054110007611en_HK
dc.identifier.scopuseid_2-s2.0-78649425131en_HK
dc.identifier.hkuros194301en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-78649425131&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume21en_HK
dc.identifier.issue6en_HK
dc.identifier.spage875en_HK
dc.identifier.epage891en_HK
dc.identifier.isiWOS:000286806000002-
dc.publisher.placeSingaporeen_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridZhang, Y=35114314500en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats