License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.538
URN: urn:nbn:de:0030-drops-39630
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3963/
Go to the corresponding LIPIcs Volume Portal

Dósa, György ; Sgall, Jiri

First Fit bin packing: A tight analysis

pdf-format:
51.pdf (0.6 MB)

Abstract

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. This means that if the optimum needs OPT bins, FirstFit always uses at most \lfloor 1.7 OPT \rfloor bins.

Furthermore we show matching lower bounds for a majority of values of OPT, i.e., we give instances on which FirstFit uses exactly \lfloor 1.7 OPT \rfloor bins.

Such matching upper and lower bounds were previously known only for finitely many small values of OPT. The previous published bound on the absolute approximation ratio of FirstFit was 12/7 \approx 1.7143. Recently a bound of 101/59 \approx 1.7119 was claimed.

BibTeX - Entry

@InProceedings{dsa_et_al:LIPIcs:2013:3963,
  author =	{Gy{\"o}rgy D{\'o}sa and Jiri Sgall},
  title =	{{First Fit bin packing: A tight analysis}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{538--549},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3963},
  URN =		{urn:nbn:de:0030-drops-39630},
  doi =		{10.4230/LIPIcs.STACS.2013.538},
  annote =	{Keywords: Approximation algorithms, online algorithms, bin packing, First Fit}
}

Keywords: Approximation algorithms, online algorithms, bin packing, First Fit
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI