A tighter bound for FFd algorithm

DOI10.1007/BF02671122zbMath0966.68228OpenAlexW2077008313MaRDI QIDQ1594856

Rongheng Li, Minyi Yue

Publication date: 16 August 2001

Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

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

zbMATH Keywords

bin-packing FFD algorithm

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (1)

Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)

Cites Work

• On the exact upper bound for the Multifit processor scheduling 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
• A new proof for the first-fit decreasing bin-packing algorithm
• An Application of Bin-Packing to Multiprocessor Scheduling

This page was built for publication: A tighter bound for FFd algorithm