A new analysis of best fit bin packing

Number of the records: 1

1.

SYSNO ASEP	0387099
Document Type	C - Proceedings Paper (int. conf.)
R&D Document Type	Conference Paper
Title	A new analysis of best fit bin packing
Author(s)	Sgall, Jiří (MU-W)_{RID, ORCID, SAI}
Source Title	Fun with Algorithms. - Heidelberg : Springer, 2012 / Kranakis E. ; Krizanc D. ; Luccio F. - ISSN 0302-9743 - ISBN 978-3-642-30346-3
Pages	s. 315-321
Number of pages	7 s.
Publication form	Print - P
Action	6th International Conference on Fun with Algorithms, FUN 2012
Event date	04.06.2012-06.06.2012
VEvent location	Venice
Country	IT - Italy
Event type	WRD
Language	eng - English
Country	DE - Germany
Keywords	problem complexity ; approximation
Subject RIV	BA - General Mathematics
R&D Projects	IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
EID SCOPUS	84861965053
DOI	10.1007/978-3-642-30347-0_31
Annotation	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.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2013

Number of the records: 1