7
$\begingroup$

Consider the following algorithm for bin packing:

  1. Initially, sort the items by their size.
  2. Put the largest item in a new bin.
  3. Fill the bin with small items in ascending order of size, up to the largest item that fits.
  4. Close the bin. If some items remain, go back to step 1.

There is a very similar algorithm for the dual problem of bin covering, and its approximation ratio for that problem is 3/2. However, I did not find this algorithm discussed in the context of bin packing.

Is anything known about its approximation ratio - how close it is to the optimal solution?

$\endgroup$
0
1
+50
$\begingroup$

We show that $\mathrm{ALG} \le (3/2) \mathrm{OPT} + 1$, and in some cases $\mathrm{ALG} \ge (3/2) \mathrm{OPT} -1/2$ even when the number of items is big enough. There is still a gap between the two results. Hope someone else can improve this result.

Consider an instance produced by your algorithm. Suppose the bins are opened in order $b_1,\ldots, b_n$. Let $b_i$ be the bin such that $i=\max\{i\neq n\mid b_i\text{ contains exactly one item}\}$. Then we can conclude that for each bin $b_j$ where $j\le i$, there exists one item with size greater than 1/2. We call these items big items. In any optimal solution, we must also use $i$ bins to pack these big items. Suppose, besides these big items, there are also $k$ items $t_1,\ldots,t_k$ in the first $i$ bins. Observing that $t_1,\ldots,t_k$ are the smallest $k$ items and the $(k+1)$-th smallest item cannot be fit in any bin with a big item, we can conclude the items in the first $i$ bins are packed in an optimal way. In the rest of the proof, we will assume each bin, except the last one, contains at least two items.

Suppose the items used in step 1 are $h_1,\cdots, h_n$ in order and the rest items from small to big are $t_1,\ldots,t_m$. We have $t_1\le\cdots\le t_m\le h_n\le\cdots \le h_1$. Suppose bin $b_i$ has a space of $s_i$ that are not used. Recall that we assume each of $b_1,\ldots,b_{n-1}$ contains at least two items. We have $s_1+\cdots+s_{n-1}<t_1+\cdots+t_m+h_n$ due to step 2 of your algorithm, thus $s_1+\cdots+s_n<t_1+\cdots+t_m+1$. Note $s_1+\cdots+s_n+t_1+\cdots+t_m+h_1+\cdots+h_n=n$ and $s_i<h_{i+1}$ for $i<n$, we have $s_1+\cdots+s_n<(n+2)/3$. This means $\mathrm{ALG} \le (3/2) \mathrm{OPT} + 1$.

On the other hand, consider an instance with the following items (from small to large), where $\epsilon$ is a small number:

$$ \left\{\frac{1}{3}-6^k\epsilon,~~\frac{1}{3}-6^{k-1}\epsilon,~~\frac{1}{3}-6^{k-1}\epsilon, ~~ \text{ for } k = n, n-1,\ldots, 1\right\}, \\ \frac{1}{3}-\epsilon, \\ \left\{\frac{1}{3}+2\times 6^{k-1}\epsilon,~~ \frac{1}{3}+3\times 6^{k-1}\epsilon,~~\frac{1}{3}+3\times 6^{k-1}\epsilon ~~ \text{ for } k = 1,\ldots, n\right\}, \\ \frac{1}{3}+2\times 6^n\epsilon. $$

The optimal solution uses $2n+1$ bins: $$ \left\{\frac{1}{3}-6^{k}\epsilon,~~ \frac{1}{3}+3\times 6^{k-1}\epsilon,~~\frac{1}{3}+3\times 6^{k-1}\epsilon ~~ \text{ for } k = 1,\ldots, n\right\}, \\ \left\{\frac{1}{3}-6^{k-1}\epsilon,~~ \frac{1}{3}-6^{k-1}\epsilon,~~\frac{1}{3}+2\times 6^{k-1}\epsilon ~~ \text{ for } k = 1,\ldots, n\right\}, \\ \frac{1}{3}-\epsilon, \frac{1}{3}+2\times 6^n\epsilon. $$ But your algorithm uses $3n+1$ bins (each bin contains two items). Hence in this case $\mathrm{ALG} = (3/2) \mathrm{OPT} -1/2$.

$\endgroup$
3
  • $\begingroup$ "Suppose, besides these big items, there are also k items t1,…,tk in the first i bins" - I do not understand: didn't you define the first i bins as bins that contain exactly one item each? $\endgroup$ Aug 10 at 17:51
  • $\begingroup$ @ErelSegal-Halevi Only $b_i$ is defined to contain exactly one item. $b_1,\ldots,b_{i-1}$ may contain multiple items. $\endgroup$
    – xskxzr
    Aug 11 at 1:12
  • $\begingroup$ Thanks, great answer! So, this algorithm is better than next-fit-decreasing, whose asymptotic approximation ratio is about 1.7, and worse than first-fit-decreasing, whose ratio is about 1.22. $\endgroup$ Aug 12 at 10:58

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.