File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Dynamic bin packing of unit fractions items

TitleDynamic bin packing of unit fractions items
Authors
Chan, JWTLam, TWWong, PWH
KeywordsBin Packing
Competitive Analysis
Online Algorithms
Issue Date2008
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2008, v. 409 n. 3, p. 521-529 How to Cite?
DOI: http://dx.doi.org/10.1016/j.tcs.2008.09.028
AbstractThis paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary times. We want to pack a sequence of unit fractions items (i.e., items with sizes 1 / w for some integer w ≥ 1) into unit-size bins, such that the maximum number of bins ever 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. In particular, 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.4942. We also show that no on-line algorithm is better than 2.428-competitive. © 2008 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152404
ISSN
0304-3975
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID
WOS:000261785400019
Funding AgencyGrant Number
Hong Kong RGCHKU-5172/03E
Nuffield FoundationNAL/01004/G
Funding Information:

This research was supported in part by Hong Kong RGC Grant HKU-5172/03E when the first author was with the Department of Computer Science, University of Hong Kong, Hong Kong. The third author's research was supported in part by Nuffield Foundation Grant NAL/01004/G.

References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChan, JWTen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorWong, PWHen_US
dc.date.accessioned2012-06-26T06:38:07Z-
dc.date.available2012-06-26T06:38:07Z-
dc.date.issued2008en_US
dc.identifier.citationTheoretical Computer Science, 2008, v. 409 n. 3, p. 521-529en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://hdl.handle.net/10722/152404-
dc.description.abstractThis paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary times. We want to pack a sequence of unit fractions items (i.e., items with sizes 1 / w for some integer w ≥ 1) into unit-size bins, such that the maximum number of bins ever 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. In particular, 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.4942. We also show that no on-line algorithm is better than 2.428-competitive. © 2008 Elsevier B.V. All rights reserved.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_US
dc.relation.ispartofTheoretical Computer Scienceen_US
dc.subjectBin Packingen_US
dc.subjectCompetitive Analysisen_US
dc.subjectOnline Algorithmsen_US
dc.titleDynamic bin packing of unit fractions itemsen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/j.tcs.2008.09.028en_US
dc.identifier.scopuseid_2-s2.0-55949118085en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-55949118085&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume409en_US
dc.identifier.issue3en_US
dc.identifier.spage521en_US
dc.identifier.epage529en_US
dc.identifier.isiWOS:000261785400019-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridChan, JWT=16021445200en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridWong, PWH=9734871500en_US
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats