First Fit bin packing: a tight analysis

0424750 - MÚ 2014 RIV DE eng C - Conference Paper (international conference)
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]
R&D Projects: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Keywords : First Fit * bin packing * online algorithms
Subject RIV: BA - General Mathematics
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.
Permanent Link: http://hdl.handle.net/11104/0230778