Input: $n$ item with sizes $s_1,...,s_n$, without lose of generality, all sizes are $\leq1$.
In addition, $s_i < \delta$ for all $i$ for some constant $\delta$.
Output: Minimal numbers of bins to pack the items, where each bin has volume 1.
The scheme used is first-fit, where if the current used bins are indexed, we insert the $i_{th}$ item to bin with the lowest index it fits into. Therefore, we open a new bin only when we can't fit an item into any bin.
Denote by $OPT$ the minimal number of required bins (for some input), and by $FF$ the number of bins output by first-fit scheme, the claim is that:
$$FF \leq OPT(1+2 \delta)+1$$
The proof is divided into cases, one when $\delta\geq {1 \over 2}$
, and the second where $\delta< {1 \over 2}$.
My problem is in the later case.
In class we were shown that when the algorithm (that uses first-fit scheme) ends running, there are at least $FF-1$ bins, such that their empty space is $<\delta$. (which I understand why)
Here a
link
to the final configuration of the algorithm to make things more clear.
Then the professor claimed that: $(FF-1)(1 - \delta) \leq OPT$.
Why is that?