Počet záznamů: 1
A new analysis of best fit bin packing
- 1.0387099 - MÚ 2013 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
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]
Grant CEP: GA AV ČR IAA100190902
Klíčová slova: problem complexity * approximation
Kód oboru RIV: BA - Obecná matematika
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.
Trvalý link: http://hdl.handle.net/11104/0219397
Počet záznamů: 1