A simple proof of the inequality MFFD(L) 71 60OPT(L)+1,L for the MFFD bin-packing algorithm

DOI10.1007/BF02011198MaRDI QIDQ1916508zbMATH OpenWikidataFDO

Authors Minyi Yue, Lei Zhang

Publication date 8 July 1996

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

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

zbMATH Keywords

bin-packingFFD algorithmMFFD

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

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 simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case
• A tight lower bound for optimal bin packing
• A new proof for the first-fit decreasing bin-packing algorithm
• FFD bin packing for item sizes with uniform distributions on \([0,\frac12]\).
• An improved lower bound for the bin packing problem
• The Bin‐Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP
• Bin packing with ``largest in bottom constraint: tighter bounds and generalizations

Cites work

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

Cited in

(14)

• 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
• An improved two-machine flowshop scheduling with intermediate transportation
• SINGLE MACHINE SCHEDULING WITH JOB DELIVERY TO MINIMIZE MAKESPAN
• A new proof for the first-fit decreasing bin-packing algorithm
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
• Single-machine scheduling with periodic maintenance to minimize makespan revisited
• 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
• Improved approaches to minimize the makespan on single-machine scheduling with periodic preventive maintenance activities
• Updated estimates for algorithms for packing 2-bar charts in a strip

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

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