First Fit bin packing: A tight analysis
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10190764" target="_blank" >RIV/00216208:11320/13:10190764 - isvavai.cz</a>
Alternative codes found
RIV/67985840:_____/13:00424750
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2013.538" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.STACS.2013.538</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2013.538" target="_blank" >10.4230/LIPIcs.STACS.2013.538</a>
Alternative languages
Result language
angličtina
Original language name
First Fit bin packing: A tight analysis
Original language description
In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. FirstFit algorithm packs each item into the first bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. In early seventies it was shown that the asymptotic approximation ratio of FirstFit bin packing is equal to 1.7. We prove that also the absolute approximation ratio for FirstFit bin packing is exactly 1.7.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
ISBN
978-3-939897-50-7
ISSN
1868-8969
e-ISSN
—
Number of pages
12
Pages from-to
538-549
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Germany
Event location
Kiel
Event date
Feb 27, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—