2
$\begingroup$

I am with the phone so I would be more verbose when I will have a pc on hand, if you desire.

The first fit algorithm for approximating the bin packing problem (NP-hard) is a $2$-approximation for the optimum. Can you show me a concrete worst case showing that $2$ is a good (or bad) extimate for the bound?

$\endgroup$
  • 2
    $\begingroup$ That's a nice exercise that is best done on your own. Try a few examples, or go through the analysis of the first fit algorithm and see what would have to happen for it to be tight. $\endgroup$ – Yuval Filmus Feb 23 '17 at 20:23
  • $\begingroup$ @YuvalFilmus will I be able to get exactly $2$ or something smaller? $\endgroup$ – Nisba Feb 23 '17 at 22:30
  • $\begingroup$ Not necessarily exactly 2, but $2-\epsilon$ for any positive $\epsilon$. $\endgroup$ – Yuval Filmus Feb 24 '17 at 2:31
  • $\begingroup$ @YuvalFilmus, no idea, can you give me an hint please? $\endgroup$ – Nisba Feb 26 '17 at 11:43
  • 1
    $\begingroup$ Fair enough. I guessed that it's an easy homework question that you were having trouble with, but in this case my guess was wrong. Unfortunately many of the questions here are of the former type. $\endgroup$ – Yuval Filmus Feb 26 '17 at 16:57
2
$\begingroup$

The approximation ratio of first fit for bin packing is actually 1.7 rather than 2. See Dósa and Sgall, First fit bin packing: a tight analysis. The paper contains references which prove a matching lower bound.

$\endgroup$
  • $\begingroup$ The question is about the concrete example of the worst-case. If the paper gives it, could you point to that? $\endgroup$ – Dmytro Bogatov Dec 19 '17 at 0:13
  • $\begingroup$ Have you taken a look at the paper? $\endgroup$ – Yuval Filmus Dec 19 '17 at 6:21
  • $\begingroup$ Yep. Although I have not read it it in detail. It is clear that ratio is 1.7, but the concrete example of an input is not that obvious. Pardon me, if I missed it. But would you mind updating your answer including such input example? $\endgroup$ – Dmytro Bogatov Dec 20 '17 at 9:24
  • $\begingroup$ I can do no better than read the paper, which you can also do. $\endgroup$ – Yuval Filmus Dec 20 '17 at 18:42
  • 1
    $\begingroup$ The example input is there. You'll have to read it yourself. It's essentially given in Lemma 4.1. $\endgroup$ – Yuval Filmus Dec 21 '17 at 20:19
0
$\begingroup$

Just so you can check yourself that the approximation ratio will be better than 2: Assume you have items that can be fit into k bins, each bin having capacity one. So far you have used 2k-1 bins, so you want to prove that the next item fits into one of the 2k-1 bins.

Let the next item have size c. We have c ≤ 1/2: If c was greater than 0.5, then we would have 2k items > 0.5 for a total size > k, which couldn't fit into k bits.

And there is a bin that contains at most 1 - c so the next item fits into that bin: Otherwise, we have 2k-1 bins containing > 1-c ≥ 1/2, so we have more than 2k-2 bins containing 1/2, 1 bin containing more than 1-c, plus an item of size c, for a total > k. This doesn't fit into k bins.

$\endgroup$
  • $\begingroup$ When we say that the approximation ratio is better than 2, we meant that the algorithm is a $c$-approximation for some $c < 2$. It's not enough that we always get a solution which is better than twice the optimum. In other words, the approximation ratio is a supremum that isn't necessarily achieved. $\endgroup$ – Yuval Filmus Feb 26 '17 at 16:21

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.