First Fit bin packing: A tight analysis
Identifikátory výsledku
Kód výsledku v 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>
Nalezeny alternativní kódy
RIV/67985840:_____/13:00424750
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
First Fit bin packing: A tight analysis
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
First Fit bin packing: A tight analysis
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2013
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
ISBN
978-3-939897-50-7
ISSN
1868-8969
e-ISSN
—
Počet stran výsledku
12
Strana od-do
538-549
Název nakladatele
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Místo vydání
Dagstuhl, Germany
Místo konání akce
Kiel
Datum konání akce
27. 2. 2013
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—