Abstract
The first fit decreasing (FFD) heuristic algorithm is one of the most famous and most studied methods for an approximative solution of the bin-packing problem. For a listL, let OPT(L) denote the minimal number of bins into whichL can be packed, and let FFD(L) denote the number of bins used by FFD. Johnson[1] showed that for every listL, FFD(L)≤11/9OPT(L)+4. His proof required more than 100 pages. Later, Baker[2] gave a much shorter and simpler proof for FFD(L)≤11/9 OPT(L)+3. His proof required 22 pages. In this paper, we give a proof for FFD(L)≤11/9 OPT(L)+1. The proof is much simpler than the previous ones.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D.S. Johnson: Near-Optimal Bin-Packing Algorithms. Doctoral thesis, M.I.T., Cambridge, Mass., 1973.
B.S. Baker: A New Proof for the First-Fit Decreasing Bin-Packing Algorithm,J. Algorithms,6 (1985), 49–70.
E.G. Coffman Jr., M.R. Garey and D.S. Johnson: An Application of Bin-Packing to Multiprocessor Scheduling,SIAM J. Comput,7 (1987), 1–17.
Minyi Yue: On the Exact Upper Bound for the Multifit Processor Scheduling Algorithm,Operations Research in China (ed. Minyi Yue), 233–260,Ann. Oper. Res.,24 (1990).
Author information
Authors and Affiliations
Additional information
In Commemoration of the 15th Anniversary of the Acta Mathematicae Applicatae Sinica
This work was done when the author visited the Forschungsinstitut für Diskrete Mathematik of Universität Bonn during the period from September to December, 1990. Supported by Sonderforshungsbereich 303 (DFG).
Rights and permissions
About this article
Cite this article
Yue, M. A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm. Acta Mathematicae Applicatae Sinica 7, 321–331 (1991). https://doi.org/10.1007/BF02009683
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02009683