Journal article
Tighter bounds of the First Fit algorithm for the bin-packing problem
B Xia, Z Tan
Discrete Applied Mathematics | ELSEVIER SCIENCE BV | Published : 2010
Abstract
In this paper, we present improved bounds for the First Fit algorithm for the bin-packing problem. We prove CFF(L)≤17/10C*(L)+7/10 for all lists L, and the absolute performance ratio of FF is at most 12/7. © 2010 Elsevier B.V. All rights reserved.
Grants
Awarded by National Natural Science Foundation of China
Funding Acknowledgements
We are grateful to two anonymous referees for their constructive suggestions regarding an earlier version of our paper. The second author's work was supported by the National Natural Science Foundation of China (10971191, 60021201) and Zhejiang Provincial Natural Science Foundation of China (Y607079).