Tight absolute bound for first fit decreasing bin-packing: FFD(L) 11/9 OPT(L)+6/9
From MaRDI portal
Publication:392175
Recommendations
- The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
- 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
- scientific article; zbMATH DE number 1560341
- Tighter bounds of the First Fit algorithm for the bin-packing problem
- The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
- A new proof for the first-fit decreasing bin-packing algorithm
- A tight lower bound for optimal bin packing
- A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm
- Bin packing with discrete item sizes, part II: Tight bounds on First Fit
Cites work
- A new proof for the first-fit decreasing bin-packing algorithm
- 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
- A tighter bound for FFd algorithm
- On the machine scheduling problem with job delivery coordination
- The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
Cited in
(33)- Tighter bounds of the First Fit algorithm for the bin-packing problem
- Compact integer linear programming formulations for the temporal bin packing problem with fire-ups
- Scheduling with interjob communication on parallel processors
- Scheduling with interjob communication on parallel processors
- Batched bin packing revisited
- Minmizing service span with batch-position-based learning effects
- Several methods of analysis for cardinality constrained bin packing
- Several methods of analysis for cardinality constrained bin packing
- The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
- Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation
- 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
- Scheduling with job delivery coordination on single machine
- A 71/60 theorem for bin packing
- Integrated scheduling on a batch machine to minimize production, inventory and distribution costs
- Single machine scheduling with job delivery to multiple customers
- The tight absolute bound of First Fit in the parameterized case
- A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm
- Approximation and online algorithms for multidimensional bin packing: a survey
- An introduction to stochastic bin packing-based server consolidation with conflicts
- Integrated optimization of material supplying, manufacturing, and product distribution: models and fast algorithms
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- Non-resumable scheduling on a single bounded parallel-batch machine with periodic maintenance
- A variable neighborhood search approach to solve the order batching problem with heterogeneous pick devices
- Open-end bin packing: new and old analysis approaches
- A new proof for the first-fit decreasing bin-packing algorithm
- Mathematical models and approximate solution approaches for the stochastic bin packing problem
- A tight approximation algorithm for problem \(P2\rightarrow D|v=1,c=1|C_{\max }\)
- Two parallel machines scheduling with two-vehicle job delivery to minimize makespan
- The Parametric Behavior of the First-Fit Decreasing Bin Packing Algorithm
- Parallel machine scheduling with job delivery coordination
- scientific article; zbMATH DE number 1560341 (Why is no real title available?)
- Bin packing under linear constraints
- Max-min bin packing algorithm and its application in nano-particles filling
This page was built for publication: Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392175)
