A new analysis of best fit bin packing

0387099 - MÚ 2013 RIV DE eng C - Conference Paper (international conference)
Sgall, Jiří
A new analysis of best fit bin packing.
Fun with Algorithms. Heidelberg: Springer, 2012 - (Kranakis, E.; Krizanc, D.; Luccio, F.), s. 315-321. Lecture Notes in Computer Science, 7288. ISBN 978-3-642-30346-3. ISSN 0302-9743.
[6th International Conference on Fun with Algorithms, FUN 2012. Venice (IT), 04.06.2012-06.06.2012]
R&D Projects: GA AV ČR IAA100190902
Keywords : problem complexity * approximation
Subject RIV: BA - General Mathematics
http://link.springer.com/chapter/10.1007%2F978-3-642-30347-0_31

We give a simple proof and a generalization of the classical result which says that the (asymptotic) approximation ratio of BestFit algorithm is 1.7. We generalize this result to a wide class of algorithms that are allowed to pack the incoming item to any bin with load larger than 1/2 (if it fits), instead to the most full bin, and at the same time this class includes the bounded-space variants of these algorithms.
Permanent Link: http://hdl.handle.net/11104/0219397