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

DOI10.1016/0196-6774(85)90018-5zbMath0563.68042OpenAlexW2086102640MaRDI QIDQ3677174

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

heuristic algorithmsbin packingworst-case behavior

Mathematics Subject Classification ID

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

Related Items (18)

A 71/60 theorem for bin packing ⋮ Approximate strip packing: revisited ⋮ A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem ⋮ Homogeneous grouping of non-prime steel products for online auctions: a case study ⋮ 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 simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm ⋮ Tighter bounds of the First Fit algorithm for the bin-packing problem ⋮ Parallel approximation algorithms for bin packing ⋮ Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\) ⋮ 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 ⋮ 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 3/2-approximation for big two-bar charts packing ⋮ Two-bar charts packing problem ⋮ The FFD algorithm for the bin packing problem with kernel items ⋮ A tighter bound for FFd algorithm

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