Distributing stones into buckets (not trivial) / Integer Bin Packing Upper bound

Question

Suppose you have k stones and m stone types You have f1 stones from the first type, f2 from the second and so on.

(i.e. sum(f_i) = k).

In addition, we are given a positive integer r.

What is the minimal number of buckets needed, such that we could distribute the stone types into buckets where the size of every bucket is no more than r? (We also know that for every i, f_i <= r).

This question is actually some kind of bin packing, so I'm not sure it has an exact answer but can we give it an upper bound?

An example of a trivial upper bound is m, as this will allow us to pack each stone type in his own bucket.

An example of a bound which doesn't work is k/r. The reason is that if k=9, r=3 and we have 5 stone types, f1 = 2, f2 = 2, f3 = 2, f4 = 2, f5=1,

Then no matter how we partition the stone types, there has to be a bucket of size >= 4.

All stones from the same type has to go to the same bucket.

Any suggestions :) ?

EDIT: m and the f_i's are unknown, and I'm looking for a bound which enables me to distribute the stones for all (m,f_i's) combination.

Another example: Suppose that r = 3. I'll prove that k/2 buckets are enough:

Let's denote by x the number of types for which there are 3 stones. y will denote the number of type from which there are exactly 2 stones, and z will the denote the number of single-stone types.

By definition: 3x + 2y + z = k. We can allocate x buckets for the 3-stones types.

If (y > z) {first case}: Fit one of the y types, together with one of the z types in a bucket {we have z such buckets}.

Fit the rest of the y types one at a bucket.

Since y > z we have used exactly x+y buckets, and since 3x + 2y + z = k => x+y <= k/2.

If (z >= y) {second case}: It's easy to see that we can fit all stones in k/3 buckets (every bucket can be full, containing exactly 3 stones).

Also, for r=3, this bound it tight (if x=z=0 and y=k/2, then we need exactly k/2 buckets).

Now the question is: does the k/2 buckets bound hold for all r values?

I can show that a lower bound (i.e. a tight instance) of 2k/(r+1) buckets, but it's pretty far from k/2. Can anyone tighten the bound?

Answer 1

You can use the first-fit algorithm for the bin packing problem with almost no modifications necessary:

1. Generate a list L containing m integers, each represents the number of stones of each type.
2. Sort the list in descending order.
3. Create a new bucket
4. Run through L from the beginning to end, if adding the current element of L to the bucket doesn't exceed r, add to the bucket and remove it from L.
5. If L is empty, return the number of buckets. Else go back to step 3.

This algorithm is an approximation of 11/9*OPT + 6/9, which is pretty decent and in most cases given a very good result.

The running type of this algorithm is O(m log m). If m is not given, to create the list you need to count the number of stones of each type, which takes O(L) time and the whole procedure will take O((m log m) + L) time.