Tight absolute bound for first fit decreasing bin-packing: FFD(L) 11/9 OPT(L)+6/9

DOI10.1016/J.TCS.2013.09.007zbMATH Open1359.90116OpenAlexW179790402MaRDI QIDQ392175FDOQ392175

Authors: Rongheng Li, Xin Han, Zsolt Tuza, György Dósa 

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.09.007

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

zbMATH Keywords

bin packingfirst fit decreasingtight bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Cites Work

• 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
• 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
• A new proof for the first-fit decreasing bin-packing algorithm

Cited In (33)

• Compact integer linear programming formulations for the temporal bin packing problem with fire-ups
• Tighter bounds of the First Fit algorithm for the bin-packing problem
• Scheduling with interjob communication on parallel processors
• Scheduling with interjob communication on parallel processors
• Batched bin packing revisited
• Several methods of analysis for cardinality constrained bin packing
• Several methods of analysis for cardinality constrained bin packing
• Minmizing service span with batch-position-based learning effects
• 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
• Scheduling with job delivery coordination on single machine
• 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 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
• Non-resumable scheduling on a single bounded parallel-batch machine with periodic maintenance
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• 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
• Title not available (Why is that?)
• 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)