A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm

DOI10.1007/BF02011198zbMath0856.68073WikidataQ56212222 ScholiaQ56212222MaRDI QIDQ1916508

Minyi Yue, Lei Zhang

Publication date: 8 July 1996

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

zbMATH Keywords

bin-packingFFD algorithmMFFD

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (9)

An improved two-machine flowshop scheduling with intermediate transportation ⋮ A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem ⋮ Single-machine scheduling with periodic maintenance to minimize makespan revisited ⋮ 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 ⋮ SINGLE MACHINE SCHEDULING WITH JOB DELIVERY TO MINIMIZE MAKESPAN ⋮ A 3/2-approximation for big two-bar charts packing ⋮ Two-bar charts packing problem

Cites Work

• A 71/60 theorem for bin packing
• A new proof for the first-fit decreasing bin-packing algorithm

This page was built for publication: A simple proof of the inequality \(MFFD(L)\leq {71\over 60}\text{OPT}(L)+1,L\) for the \(MFFD\) bin-packing algorithm