File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Dynamic bin packing of unit fractions items

TitleDynamic bin packing of unit fractions items
Authors
Issue Date2005
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 32nd International Colloqium on Automata, Languages and Programming (ICALP 2005), Lisbon, Portugal, 11-15 July 2005. In Lecture Notes In Computer Science, 2005, v. 3580, p. 614-626 How to Cite?
AbstractThis paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary time. We want to pack a sequence of unit fractions items (i.e., items with sizes 1/ω for some integer w ≥ 1) into unit-size bins such that the maximum number of bins used over all time is minimized. Tight and almost-tight performance bounds are found for the family of any-fit algorithms, including first-fit, best-fit, and worst-fit. We show that the competitive ratio of best-fit and worst-fit is 3, which is tight, and the competitive ratio of first-fit lies between 2.45 and 2.4985. We also show that no on-line algorithm is better than 2.428-competitive. This result improves the lower bound of dynamic bin packing problem even for general items. © Springer-Verlag Berlin Heidelberg 2005.
DescriptionLNCS v. 3580 entitled: Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Proceedings
Persistent Identifierhttp://hdl.handle.net/10722/60598
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2010-05-31T04:14:42Z-
dc.date.available2010-05-31T04:14:42Z-
dc.date.issued2005en_HK
dc.identifier.citationThe 32nd International Colloqium on Automata, Languages and Programming (ICALP 2005), Lisbon, Portugal, 11-15 July 2005. In Lecture Notes In Computer Science, 2005, v. 3580, p. 614-626en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/60598-
dc.descriptionLNCS v. 3580 entitled: Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Proceedings-
dc.description.abstractThis paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary time. We want to pack a sequence of unit fractions items (i.e., items with sizes 1/ω for some integer w ≥ 1) into unit-size bins such that the maximum number of bins used over all time is minimized. Tight and almost-tight performance bounds are found for the family of any-fit algorithms, including first-fit, best-fit, and worst-fit. We show that the competitive ratio of best-fit and worst-fit is 3, which is tight, and the competitive ratio of first-fit lies between 2.45 and 2.4985. We also show that no on-line algorithm is better than 2.428-competitive. This result improves the lower bound of dynamic bin packing problem even for general items. © Springer-Verlag Berlin Heidelberg 2005.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleDynamic bin packing of unit fractions itemsen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=409&issue=3&spage=521&epage=529&date=2008&atitle=Dynamic+bin+packing+of+unit+fractions+itemsen_HK
dc.identifier.emailChan, WT: wtchan@cs.hku.hken_HK
dc.identifier.emailLam, TW: twlam@cs.hku.hk-
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturepostprint-
dc.identifier.scopuseid_2-s2.0-26444553310en_HK
dc.identifier.hkuros154830en_HK
dc.identifier.hkuros102690-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-26444553310&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3580en_HK
dc.identifier.spage614en_HK
dc.identifier.epage626en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, WT=7403918060en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK
dc.customcontrol.immutablesml 160105 - merged-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats