Tighter bounds of the First Fit algorithm for the bin-packing problem
From MaRDI portal
Publication:602685
DOI10.1016/j.dam.2010.05.026zbMath1231.05066OpenAlexW2079141386WikidataQ56212219 ScholiaQ56212219MaRDI QIDQ602685
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
Related Items
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
