First Fit bin packing: a tight analysis

0424750 - MÚ 2014 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Dósa, G. - Sgall, Jiří
First Fit bin packing: a tight analysis.
30th International Symposium on Theoretical Aspects of Computer Science. Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2013 - (Portier, N.; Wilke, T.), s. 538-549. Leibniz International Proceedings in Informatics, 20. ISBN 978-3-939897-50-7. ISSN 1868-8969.
[International Symposium on Theoretical Aspects of Computer Science (STACS 2013), /30./. Kiel (DE), 27.02.2013-02.03.2013]
Grant CEP: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Klíčová slova: First Fit * bin packing * online algorithms
Kód oboru RIV: BA - Obecná matematika
http://drops.dagstuhl.de/opus/volltexte/2013/3963/

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.
Trvalý link: http://hdl.handle.net/11104/0230778