This is the problem:
For those who don't know Bin Packing: We get online input of 1 item each time with size in (0,1]. We use First-Fit. (As the name suggests, we put each item we get in the first available bin, so that the total size of the items in a bin won't be more than 1.)
The only limitations we have are:
- No bin can exceed $1$.
- No bin can hold more then $K$ items.
I need to prove that for any given $K$, the competitive ratio ("First_fit/Opt," meaning "First-Fit/Optimal") is less than or equal to 3.
I tried to do it using induction:
Our premiss is that for any given $K$, the competitive ratio is less than 3.
If we check for $K=1$, we get ratio of $1<3$.
Let's use our premiss, and check if it works for $K=K+1$.
If we add more slot for each bin, the FF algorithm can only improve (since more might get into less bins), but the problem is that OPT might also improve.
What am I missing?
Thank you
Edit:
An example of FF vs. OPT: For an input of $K=3$:
$\epsilon*3,1/3+\epsilon,1/3+\epsilon,1/3+\epsilon,1/3+\epsilon,1/2+\epsilon,1/2+\epsilon,1/2+\epsilon$
FF will do: $(\epsilon*3) , (1/3+\epsilon*2),(1/3+\epsilon*2),(1/2+\epsilon),(1/2+\epsilon),(1/2+\epsilon),(1/2+\epsilon)$
$7$ bins.
OPT will do: $(1/2+\epsilon,1/3+\epsilon,\epsilon),(1/2+\epsilon,1/3+\epsilon,\epsilon),(1/2+\epsilon,1/3+\epsilon,\epsilon),(1/2+\epsilon,1/3+\epsilon)$
$4$ bins.
So for this example the ratio is $7/4$.
I got some inspiration after looking at the wiki page for a bit. The property used to prove the bound in the case $K=\infty$ is that you can never have two bins (or more) in the first-fit approach, that are less than half full. The second "less than half full" bin should never be created since the items it contains should first get put into the first "less than half full" bin. This yields an inequality that eventually yields the bound.
In the present case of $K<\infty$, the property should be rephrased into: there can never be two bins (or more) that contain strictly less than $K$ items, and that are less than half full.
Say you have $n$ items of weight $w_i$, $1\le i\le n$. Say first-fit yields $A$ bins. Count the number of bins that contain the maximum number of items $K$, and let that number $A_1$. Let the number of remaining bins $A_2$, those bins can still accept new items and most of them should be at least half-full. Specifically, $A_2-1 < 2\sum_{i=1}^n w_i$. Because $\sum_i w_i$ is a lower bound on the minimum number of bins $\mathrm{opt}$, you get $A_2-1<2\mathrm{opt}$. Since everyone is an integer, you can actually have $A_2\le 2 \mathrm{opt}$.
To complete the proof, you just notice that $A_1\le \frac nK \le\mathrm{opt}$. When you put everything together you obtain $A=A_1+A_2\le 3\mathrm{opt}$.