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
From MaRDI portal
Publication:1198607
DOI10.1007/BF02009683zbMath0753.05022OpenAlexW4238573359WikidataQ56212216 ScholiaQ56212216MaRDI QIDQ1198607
Publication date: 16 January 1993
Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02009683
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of packing and covering (05B40)
Related Items (20)
Approximate strip packing: revisited ⋮ A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem ⋮ Bin packing with rejection revisited ⋮ Improved algorithms for two single machine scheduling problems ⋮ The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\) ⋮ Tighter bounds of the First Fit algorithm for the bin-packing problem ⋮ On the machine scheduling problem with job delivery coordination ⋮ Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\) ⋮ Single-machine scheduling with periodic maintenance to minimize makespan revisited ⋮ Three-Bar Charts Packing Problem ⋮ A 4/3 OPT+2/3 approximation for big two-bar charts packing problem ⋮ An improved approximation for packing big two-bar charts ⋮ Approximation algorithms for time constrained scheduling ⋮ Two-machine scheduling with periodic availability constraints to minimize makespan ⋮ A 3/2-approximation for big two-bar charts packing ⋮ Two-bar charts packing problem ⋮ Solving robust bin-packing problems with a branch-and-price approach ⋮ The FFD algorithm for the bin packing problem with kernel items ⋮ A new heuristic algorithm for the machine scheduling problem with job delivery coordination ⋮ A tighter bound for FFd algorithm
Cites Work
This page was built for publication: 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
