1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

We have $u = 1 - e$ where $u$ is used space and $e$ is empty space.

Since for at least $FF - 1$ bins we have $e < \delta$ (which you understand why), for those we also have $1- e > 1 - \delta$ or $u > 1-\delta$.

So in at least $FF - 1$ bins we use at least $1 - \delta$ space. Since each bin has maximum size $1$ we can also say that at least $FF - 1$ bins are at least $1 - \delta$ fraction full. In other words, we have at least $(FF - 1)(1 - \delta)$ bins worth of 'stuff', so that must be less than or equal to the optimal amount of bins we need to use (or else we'd have more stuff than that could fit).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.