主观题：Better bound for FFD

The FFD algorithm for bin packing achieves the following bounds:
$$FFD(L)\le (11/9)OPT(L)+1$$, for all $$L$$.

(1) Please show that $$FFD(L)\le (3/2)OPT(L)$$, for all $$L$$, with the above inequality.

(2) Prove that the factor $$3/2$$ is the best possible unless P=NP (note that deciding if two bins are sufficient to accommodate a set of items is NP-complete).






答案：