Talk:Bin packing problem

From Wikipedia, the free encyclopedia

You have new messages (last change).
  • The Best Fit Decreasing and First Fit Decreasing strategies use no more than 11/9 OPT + 1 bins (where OPT is the number of bins given by the optimal solution).

I think this needs a citation. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms only proves 11/9 OPT + 4. Is this in Vazirani? Also, the FF/BF worst case of 17/10 OPT + 2 might be worth mentioning. CRGreathouse 21:04, 27 June 2006 (UTC)

Great feedback, thanks. There might be a better bound than "+4", that is a very old paper, but I don't have the sources with me right now, so I changed it to "+4". Deco 23:50, 27 June 2006 (UTC)
I did eventually come across the bounds you originally posted, so I put it back with a reference. CRGreathouse (t | c) 15:18, 13 October 2006 (UTC)
Retrieved from "http://en.wikipedia.org../../../b/i/n/Talk%7EBin_packing_problem_f334.html"