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

DOI10.1007/BF02882754MaRDI QIDQ1373809zbMATHOpenAlexFDO

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

zbMATH Keywords

bin-packing problem

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(9)

• A 4/3 OPT+2/3 approximation for big two-bar charts packing problem
• FFD bin packing for item sizes with uniform distributions on \([0,\frac12]\).
• A 3/2-approximation for big two-bar charts packing
• Two-bar charts packing problem
• Three-Bar Charts Packing Problem
• An improved approximation for packing big two-bar charts
• A posteriori analysis of the algorithms for two-bar charts packing problem
• 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

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)