First-Fit-Decreasing algorithm packs items of size at most 1 into bins of capacity 2

Question

Consider the bin packing problem where we are given item sizes $a_1,\dots, a_n \in (0, 1)$, and all bins have capacity 2. The task is to pack the items in as few bins as possible, such that the total size of items in each bin is at most 2.

Is it possible to show that the First-Fit-Decreasing algorithm computes an asymptotic 3/2-approximation of an optimal solution, using at most $\frac{3}{2}\text{OPT}+1$ bins? The First-Fit-Decreasing algorithm sorts the items in order of non-increasing size, and the next piece is always packed into the first bin in which it fits.

What I have been able to do is to show that the First-Fit algorithm, which doesn't sort the items by their sizes first, provides a $2\text{OPT}+1$ guarantee: Assume that we open $l$ bins, then for $1≤i≤l−1$, we know that the sum of the piece sizes in bins i and i+1 must be at least 2. Thus, if we let $\text{SIZE}$ denote the total size of the input items, then $$ \text{SIZE}≥2(l−1)/2=l−1 $$ which implies that $$ l≤\text{SIZE}+1 $$ In the best case each bin is filled to capacity such that each bin has a total piece size of 2. Therefore, $2\text{OPT}≥\text{SIZE}$. Thus, we get $l≤2\text{OPT}+1$.

Answer 1

Suppose we have used First-Fit-Decreasing algorithm to open $\ell$ bins.

Consider any used bin except the last one. Name it $B$.

Consider the moment the total piece size of $B$ became greater than $1$, when an item of size $u$ was added. There are two cases.

• $u\le\frac23$.
  Then all items after this item is of size at most $\frac23$. The algorithm would have added them one by one to $B$ until the total piece size in it is less than $\frac23$ away from $2$.
• $u>\frac23$.
  Then the first item in $B$ is of size $\ge u>\frac23$. So the total piece size in $B$ is $>\frac23+\frac23=\frac43$.

In all cases, the total piece size in $B$ is $>\frac43$. Hence the total piece size in all used bins is $>(\ell-1)\frac43$.

"In the best case each bin is filled to capacity such that each bin has a total piece size of $2$." Therefore, $2\text{OPT}≥(\ell-1)\frac43$, which is what we want.