Coauthor: György Dósa

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. First Fit 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. Best Fit algorithm packs each item into the most full 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 First Fit and Best Fit bin packing algorithm is equal to 1.7. We give a new and simple analysis that proves the same asymptotic ratio. Furthemore, building on this method, we prove that also the absolute approximation ratio for First Fit bin packing is exactly 1.7. This means that if the optimum needs OPT bins, First Fit always uses at most ⌊1.7OPT ⌋ bins. We also show matching lower bounds for a majority of values of OPT, i.e., we give instances on which First Fit uses exactly ⌊1.7OPT⌋ 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 First Fit was 12/7 ≈ 1.7143. Recently a bound of 101/59 ≈ 1.7119 was claimed.