I have a question concerning an online optimization algorithm:
A shipping department has to pack $n$ objects of different weight $p_1 . . . p_n$ in boxes of the same capacity $P$ . We would like to arrange the items to be shipped in a minimum number of boxes. The items arrive one by one and any item that arrives must be immediately placed in a box. We consider an online algorithm that starts with an open box and arranges the objects randomly according to the capacity in the open boxes and opens a new box only if the object cannot fit into any open box.
Let $opt$-number of box is the solution of its offline algorithm counterpart, that means the offline algorithm know in advance all the weights $p_1 . . . p_n$ so that it can always choose the most efficient way of packing (with smallest number of box)
I have to show that:
$l \le 2\cdot opt + 1$
where $l$ is the number of box returned by online algorithm
My attempt:
We denote the $i$-th box by $B_i$ and $B^* := B_i \cup\cdots\cup B_{l-1}$. We consider $\bar p$ as the first object that can not fit into any the $1,2\dots(l-1)$-th boxes, so that $\bar p$ has to be put in the $l$-th box, i.e., the last box. Hence we have $(l-1)$ inequalities.
$$\forall i=1,\ldots,l-1:\sum_{s \in B_i} p_s +\bar p > P \quad( \text{at the time } \bar p \text{ has been put into } B_l)$$
We sum them all and get $$\sum_{s \in B^*} p_s +(l-1)\bar p > (l-1)P \quad( \text{at the time } \bar p \text{ has been put into } B_l).$$
Then we get $$\frac{\sum_{s \in B^*} p_s}{P} +(l-1)\frac{\bar p}{P} +1> l\quad( \text{at the time } \bar p \text{ has been put into } B_l).$$
It is obvious that: $$opt>\frac{\sum_{s \in B^*} p_s}{P}.$$
Now in order to prove the inequality I just need to prove that: $$opt> (l-1)\frac{\bar p}{P}$$
But now I get stuck and cannot move on. Could you give me some suggestion ?
Thank you in advance !