1
$\begingroup$

So I know the Next Fit Bin Packing algorithm is bounded by two times the optimal solution for the problem, but I can not think of an order of arriving elements that actually takes twice the number of bins necessary.

Something like:

50 -> 25 -> 50 -> 25 -> 50 -> 25 -> 50 -> 25

would result in:

|25| |25| |25| |25|

|50| |50| |50| |50|

bins with next fit while the optimal solution would be:

|50| |50| |25 * 2|

|50| |50| |25 * 2|

Which is only one bin difference. So what actually is the worst order of elements for the next fit bin packing algorithm?

$\endgroup$
  • 1
    $\begingroup$ A bound is not the same as a tight bound. Not saying that it's not tight, just saying that it's an upper bound. For example, for knapsack, the easy proof for the "next fit" heuristic gives a factor two bound, but a slightly more involved proof gives something like a factor 3/2 upper bound. $\endgroup$ – Pål GD Jan 14 '17 at 15:03
  • 1
    $\begingroup$ This may be helpful labri.fr/perso/eyraud/pmwiki/uploads/Main/BinPackingSurvey.pdf. See figure 2.1 $\endgroup$ – drzbir Jan 14 '17 at 15:54
  • $\begingroup$ @PålGD Make an answer? $\endgroup$ – Yuval Filmus Jan 14 '17 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.