A new proof for the first-fit decreasing bin-packing algorithm

DOI10.1016/0196-6774(85)90018-5MaRDI QIDQ3677174zbMATH OpenOpenAlexFDO

Authors Brenda S. Baker

Publication date 1985

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(85)90018-5

zbMATH Keywords

bin packingheuristic algorithmsworst-case behavior

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• 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
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
• The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)
• A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm

Cited in

(20)

• A 71/60 theorem for bin packing
• Parallel approximation algorithms for bin packing
• 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
• The FFD algorithm for the bin packing problem with kernel items
• Worst-case analysis of fast heuristics for packing squares into a square
• 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
• Homogeneous grouping of non-prime steel products for online auctions: a case study
• Approximate strip packing: revisited
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
• 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
• k-times bin packing and its application to fair electricity distribution
• Max-min and 1-bounded space algorithms for the bin packing problem

This page was built for publication: A new proof for the first-fit decreasing bin-packing algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3677174)