2013/01/01 by György Dósa, Jiřı́ Sgall · 2 citations
Engineering · Mathematics · #Optimization and Packing Problems #Advanced Manufacturing and Logistics Optimization #graph theory and CDMA systems #Bin packing problem #Bin #Combinatorics #Approx #Matching (statistics) #Upper and lower bounds #Mathematics #Approximation algorithm #Unit (ring theory) #Discrete mathematics #Algorithm #Computer science #Statistics #Mathematical analysis
paper · doi:10.4230/lipics.stacs.2013.538
openalex publication_date 2013/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 ≈ 1.7143. Recently a bound of 101/59 ≈ 1.7119 was claimed.