A new proof for the first-fit decreasing bin-packing algorithm
From MaRDI portal
Publication:3677174
DOI10.1016/0196-6774(85)90018-5zbMath0563.68042MaRDI QIDQ3677174
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
68Q25: Analysis of algorithms and problem complexity
05B40: Combinatorial aspects of packing and covering
Related Items
Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\), Tighter bounds of the First Fit algorithm for the bin-packing problem, 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