The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items

The First-Fit-Decreasing (FFD) algorithm is one of the most famous and most studied methods for an approximative solution of the bin-packing problem. The question on the parametric behavior of the FFD heuristic for small items was raised in D. S. Johnson's thesis (1973, MIT, Cambridge, MA) and in E. G. Coffman et al. (1987, SIAM J. Comput.7, 1–17): what is the asymptotic worst-case ratio for FFD when restricted to lists with item sizes in the interval (0, α] for α ≤ . Let R^∞_FFD(α) denote the asymptotic worst-case ratio for these lists. In his thesis, Johnson gave the values of R^∞_FFD(α) for and he conjectured that

Full-size image

for all integers m ≥ 4. J. Csirik (1993, J. Algorithms15, 1–28) proved that, for all integers m ≥ 5, this conjecture is true when m is even. When m is odd, he further showed where G_m ≡ 1 + (m² + m − 1)/(m(m + 1)(m + 2)) = F_m + 1/(m(m + 1)(m + 2)). These results leave open the values of R^∞_FFD(α) for 0 < α < 1/5 that are not the reciprocals of integers. In this paper we resolve the remaining open cases.