File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleOnline algorithms for 1-space bounded 2-dimensional bin packing and square packing
Authors
KeywordsBin packing
Bounded mean
Competitive algorithms
Competitive ratio
Lower bounds
On-line algorithms
Side length
Square packings
Issue Date2013
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 19th International Computing and Combinatorics Conference (COCOON 2013), Hangzhou, China, 21-21 June 2013. In Lecture Notes in Computer Science, 2013, v. 7936, p. 506-517 How to Cite?
AbstractIn this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items) arrive one by one, each item must be packed into a square bin of unit size on its arrival without any information about future items. When packing items, 90-rotation is allowed. 1-space bounded means there is only one active bin. If the active bin cannot accommodate the coming item, it will be closed and a new bin will be opened. The objective is to minimize the total number of bins used for packing all items in the sequence. Our contributions are as follows: For 1-space bounded 2-dimensional bin packing, we propose an online packing strategy with competitive ratio 5.06. A lower bound of 3.17 on the competitive ratio is proven. Moreover, we study 1-space bounded square packing, where each item is a square with side length no more than 1. A 4.3-competitive algorithm is achieved, and a lower bound of 2.94 on the competitive ratio is given. All these bounds surpass the previously best known results. © 2013 Springer-Verlag Berlin Heidelberg.
DescriptionLNCS v. 7936 entitled: Computing and combinatorics: 19th International Conference, COCOON 2013 ... proceedings
Persistent Identifierhttp://hdl.handle.net/10722/184865
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorZhang, Yen_US
dc.contributor.authorChin, FYLen_US
dc.contributor.authorTing, HFen_US
dc.contributor.authorHan, Xen_US
dc.contributor.authorPoon, CKen_US
dc.contributor.authorTsin, YHen_US
dc.contributor.authorYe, DSen_US
dc.date.accessioned2013-07-15T10:14:45Z-
dc.date.available2013-07-15T10:14:45Z-
dc.date.issued2013en_US
dc.identifier.citationThe 19th International Computing and Combinatorics Conference (COCOON 2013), Hangzhou, China, 21-21 June 2013. In Lecture Notes in Computer Science, 2013, v. 7936, p. 506-517en_US
dc.identifier.isbn978-3-642-38767-8-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/184865-
dc.descriptionLNCS v. 7936 entitled: Computing and combinatorics: 19th International Conference, COCOON 2013 ... proceedings-
dc.description.abstractIn this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items) arrive one by one, each item must be packed into a square bin of unit size on its arrival without any information about future items. When packing items, 90-rotation is allowed. 1-space bounded means there is only one active bin. If the active bin cannot accommodate the coming item, it will be closed and a new bin will be opened. The objective is to minimize the total number of bins used for packing all items in the sequence. Our contributions are as follows: For 1-space bounded 2-dimensional bin packing, we propose an online packing strategy with competitive ratio 5.06. A lower bound of 3.17 on the competitive ratio is proven. Moreover, we study 1-space bounded square packing, where each item is a square with side length no more than 1. A 4.3-competitive algorithm is achieved, and a lower bound of 2.94 on the competitive ratio is given. All these bounds surpass the previously best known results. © 2013 Springer-Verlag Berlin Heidelberg.-
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectBin packing-
dc.subjectBounded mean-
dc.subjectCompetitive algorithms-
dc.subjectCompetitive ratio-
dc.subjectLower bounds-
dc.subjectOn-line algorithms-
dc.subjectSide length-
dc.subjectSquare packings-
dc.titleOnline algorithms for 1-space bounded 2-dimensional bin packing and square packingen_US
dc.typeConference_Paperen_US
dc.identifier.emailZhang, Y: yongzh@hku.hken_US
dc.identifier.emailChin, FYL: chin@cs.hku.hken_US
dc.identifier.emailTing, HF: hfting@cs.hku.hken_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-38768-5_45-
dc.identifier.scopuseid_2-s2.0-84884935580-
dc.identifier.hkuros215792en_US
dc.identifier.volume7936en_US
dc.identifier.spage506en_US
dc.identifier.epage517en_US
dc.publisher.placeGermany-
dc.customcontrol.immutablesml 140324-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats