Tighter bounds of the First Fit algorithm for the bin-packing problem

DOI10.1016/j.dam.2010.05.026zbMath1231.05066WikidataQ56212219 ScholiaQ56212219MaRDI QIDQ602685

Zhiyi Tan, Binzhou Xia

Publication date: 5 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.05.026

zbMATH Keywords

bin packing; worst case performance ratio; First Fit

Mathematics Subject Classification ID

05B40: Combinatorial aspects of packing and covering

Related Items

SINGLE MACHINE SCHEDULING WITH BATCH DELIVERY TO MULTIPLE CUSTOMERS IN A STAR-SHAPED NETWORK, Bin packing with ``largest in bottom constraint: tighter bounds and generalizations, Single-machine scheduling with periodic maintenance to minimize makespan revisited, On the absolute approximation ratio for first fit and related results, Online results for black and white bin packing

Cites Work

• Unnamed Item
• Unnamed Item
• A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm
• Resource constrained scheduling as generalized bin packing
• The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
• A new proof for the first-fit decreasing bin-packing algorithm
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• `` Strong NP-Completeness Results