Tighter bounds of the First Fit algorithm for the bin-packing problem
From MaRDI portal
Publication:602685
DOI10.1016/j.dam.2010.05.026zbMath1231.05066WikidataQ56212219 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
05B40: Combinatorial aspects of packing and covering
Related Items
SINGLE MACHINE SCHEDULING WITH BATCH DELIVERY TO MULTIPLE CUSTOMERS IN A STAR-SHAPED NETWORK, Analysis of a first-fit algorithm for the capacitated unit covering problem, A note on the algorithm LPT-FF for a flowshop scheduling with two batch-processing machines, 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, Integrated scheduling on a batch machine to minimize production, inventory and distribution costs, Integrated optimization of material supplying, manufacturing, and product distribution: models and fast algorithms, Bin packing problem with conflicts and item fragmentation, Batch scheduling of nonidentical job sizes with minsum criteria, A heuristic algorithm for solving triangle packing problem, Online results for black and white bin packing, Black and White Bin Packing Revisited
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
