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

DOI10.1016/J.DAM.2010.05.026zbMath1231.05066DBLPjournals/dam/XiaT10OpenAlexW2079141386WikidataQ56212219 ScholiaQ56212219MaRDI QIDQ602685

Binzhou Xia, Zhiyi Tan

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 packingworst case performance ratioFirst Fit

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40)

Related Items (14)

Black and White Bin Packing Revisited ⋮ Bin packing with ``largest in bottom constraint: tighter bounds and generalizations ⋮ Single-machine scheduling with periodic maintenance to minimize makespan revisited ⋮ A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts ⋮ Integrated scheduling on a batch machine to minimize production, inventory and distribution costs ⋮ On the absolute approximation ratio for first fit and related results ⋮ Integrated optimization of material supplying, manufacturing, and product distribution: models and fast algorithms ⋮ SINGLE MACHINE SCHEDULING WITH BATCH DELIVERY TO MULTIPLE CUSTOMERS IN A STAR-SHAPED NETWORK ⋮ Bin packing problem with conflicts and item fragmentation ⋮ A note on the algorithm LPT-FF for a flowshop scheduling with two batch-processing machines ⋮ Batch scheduling of nonidentical job sizes with minsum criteria ⋮ Analysis of a first-fit algorithm for the capacitated unit covering problem ⋮ A heuristic algorithm for solving triangle packing problem ⋮ 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

This page was built for publication: Tighter bounds of the First Fit algorithm for the bin-packing problem