Talk:Bin packing problem

From Wikipedia, the free encyclopedia

• 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)

[edit] Does sorting "greatly" increase time?

The original article had a sentence concluding that sorting, "...particularly for longer list, can greatly increase the time taken to implement the algorithm." It also says that the algorithm in question, the first fit algorithm, requires Θ(n log n) time. Typical sorting algorithms also require O(n log n) time.

Since the sort appears to be complete before the fitting algorithm begins, I would expect sorting not to add "greatly" to the time. However, I'm not completely certain about this. I would welcome references stating one way or the other.

Ken g6 02:51, 5 May 2007 (UTC)

[edit] Can you solve for the number of bins?

Is the question of how many bins (without regard to which items go in which bin) an equivalent problem? Or are there polynomial time solutions to that? —Preceding unsigned comment added by 204.94.228.3 (talk) 01:07, 1 March 2008 (UTC)

That's a good question. The usual way to approach this question is to answer the question: if we had an oracle that could tell us the exact minimum number of bins needed to pack the items into the bins, would the bin packing problem become easy? If so, then your problem is NP-hard with respect to polynomial-time Turing reductions. I suspect the answer to this is yes, but don't have a proof or a reference. Dcoetzee 04:31, 1 March 2008 (UTC)

Thanks for the response. That's a good insight. I suspect that the answer is no, because if you could guess the number of bins and then make the bin packing problem easy then you could simply solve the general bin packing problem by starting with the total weight of items / capacity of each bin and keep increasing the number of bins until you had an optimal pack. I noticed that the article says that FFD produces bins <= 1/9 * optimal bins + 1, so I'm guessing there must be some other method to determine the optimal number. I expect that's where the answer lies. —Preceding unsigned comment added by 67.162.48.73 (talk) 02:29, 4 March 2008 (UTC)