First Fit bin packing: A tight analysis

G Dósa, J Sgall - … symposium on theoretical aspects of computer …, 2013 - drops.dagstuhl.de
30th International symposium on theoretical aspects of computer …, 2013drops.dagstuhl.de
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 …
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, ie, 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.
drops.dagstuhl.de
以上显示的是最相近的搜索结果。 查看全部搜索结果