Number of the records: 1
First Fit bin packing: a tight analysis
- 1.
SYSNO ASEP 0424750 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title First Fit bin packing: a tight analysis Author(s) Dósa, G. (HU)
Sgall, Jiří (MU-W) RID, ORCID, SAISource Title 30th International Symposium on Theoretical Aspects of Computer Science. - Dagstuhl : Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2013 / Portier N. ; Wilke T. - ISSN 1868-8969 - ISBN 978-3-939897-50-7 Pages s. 538-549 Number of pages 12 s. Publication form Print - P Action International Symposium on Theoretical Aspects of Computer Science (STACS 2013), /30./ Event date 27.02.2013-02.03.2013 VEvent location Kiel Country DE - Germany Event type WRD Language eng - English Country DE - Germany Keywords First Fit ; bin packing ; online algorithms Subject RIV BA - General Mathematics R&D Projects IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) GBP202/12/G061 GA ČR - Czech Science Foundation (CSF) EID SCOPUS 84892596888 DOI 10.4230/LIPIcs.STACS.2013.538 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2014
Number of the records: 1