Počet záznamů: 1
A new analysis of best fit bin packing
- 1.
SYSNO ASEP 0387099 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název A new analysis of best fit bin packing Tvůrce(i) Sgall, Jiří (MU-W) RID, ORCID, SAI Zdroj.dok. Fun with Algorithms. - Heidelberg : Springer, 2012 / Kranakis E. ; Krizanc D. ; Luccio F. - ISSN 0302-9743 - ISBN 978-3-642-30346-3 Rozsah stran s. 315-321 Poč.str. 7 s. Forma vydání Tištěná - P Akce 6th International Conference on Fun with Algorithms, FUN 2012 Datum konání 04.06.2012-06.06.2012 Místo konání Venice Země IT - Itálie Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova problem complexity ; approximation Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd EID SCOPUS 84861965053 DOI 10.1007/978-3-642-30347-0_31 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2013
Počet záznamů: 1