#StackBounty: #optimization #approximation #heuristics #packing What is the approximation ratio of this bin-backing algorithm?

Bounty: 50

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?

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.