1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Since each used bin except the last one must have a total piece size greater than $1$, a first-fit algorithm must lead to total piece greater than $\ell-1.$ $\endgroup$
    – John L.
    Jun 7, 2023 at 19:47

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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