A simple proof of the inequality FFD(L) 11 9 OPT(L)+1, L for the FFD bin-packing algorithm
From MaRDI portal
Publication:1198607
Recommendations
- The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)
- The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items
- Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
- A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm
- The Parametric Behavior of the First-Fit Decreasing Bin Packing Algorithm
Cites work
Cited in
(28)- A new heuristic algorithm for the machine scheduling problem with job delivery coordination
- A 71/60 theorem for bin packing
- The FFD algorithm for the bin packing problem with kernel items
- The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)
- A tighter bound for FFd algorithm
- A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm
- 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
- Two-machine scheduling with periodic availability constraints to minimize makespan
- Approximate strip packing: revisited
- The Parametric Behavior of the First-Fit Decreasing Bin Packing Algorithm
- 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
- 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
- A posteriori analysis of the algorithms for two-bar charts packing problem
- Tighter bounds of the First Fit algorithm for the bin-packing problem
- 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
- On online approximation algorithms for two-stage bins
- k-times bin packing and its application to fair electricity distribution
- Max-min and 1-bounded space algorithms for the bin packing problem
- Bin packing with rejection revisited
- Improved algorithms for two single machine scheduling problems
- On the machine scheduling problem with job delivery coordination
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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198607)
