The proof of FFD(L)119OPT(L)+79

DOI10.1007/BF02882754zbMATH Open0886.68080OpenAlexW1972692576MaRDI QIDQ1373809FDOQ1373809

Authors: Rongheng Li, Minyi Yue 

Publication date: 4 May 1998

Published in: Chinese Science Bulletin (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02882754

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
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
• The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/9
• A new proof for the first-fit decreasing bin-packing algorithm

zbMATH Keywords

bin-packing problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• 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
• FFD bin packing for item sizes with uniform distributions on \([0,\frac12]\).
• Three-Bar Charts Packing Problem
• A new proof for the first-fit decreasing bin-packing algorithm
• A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem

This page was built for publication: The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)

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