The proof of \(\text{FFD}(L)\leq\frac{11}9\text{OPT}(L)+\frac79\)

DOI10.1007/BF02882754zbMath0886.68080OpenAlexW1972692576MaRDI QIDQ1373809

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)

Related Items (6)

A Posteriori Analysis of the Algorithms for Two-Bar Charts 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 ⋮ A 3/2-approximation for big two-bar charts packing ⋮ Two-bar charts packing problem

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

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