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
Chan, WTLam, TWWong, PWH
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
0302-9743
2023 SCImago Journal Rankings: 0.606
References
References in Scopus

 

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.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-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats