Worst-case analysis of the subset sum algorithm for bin packing. (Q1417595)

The authors investigate the asymptotic worst-case ratio of the subset sum heuristic for the bin packing problem (BPP). They prove a new lower bound on the optimal value of BPP and formulate a mathematical programming problem which they solve analytically. The optimal value of this program yields the upper bound \(\frac{4}{3}+\ln\left(\frac{4}{3}\right)\approx 1.6210\) on the worst-case ratio of the subset sum heuristic. It is also shown that for bounded item sizes the worst case ratio of the subset sum heuristic is inbetween that of the first fit and first fit decreasing heuristics.