Bin Packing Problem Variation with Restricted Bins & Items

[Mentallic]

I have a problem whereby I'm given an item list of size n with the value of each item being greater than zero, and need to sort them among a restricted amount of bins as evenly as possible. Additionally, each bin can hold at most k items and the number of bins is slightly greater than n/k (Giving some wiggle room to have k-1 items in some bins but k items in most).

Does this sort of problem have a name?

 

[Buzz Bloom]

http://www.seas.upenn.edu/~cit596/notes/dave/p-and-np4.html

 

[BvU]

Hi guys, no solution from me, just asking for clarification: in Buzz's reference the value of the items plays a role (the integer values in each bin have to add up to the same number). It looks as if that isn't a requirement in the post #1 case. So I thought I'd just ask: would it be Ok if I would just sort the list and place the first n/k from the sorted list in bin #1, the next n/k in bin #2 etc. ?

Probably not, because that would allow items with the same value to end up in adjacent bins -- but I can't find that restriction in the description.
On the other hand: what if the list has more than k entries for items with a particular value? Would a solution have to include assigning multiple bins to the same value in such a case ? (this time I suppose a "yes"...)

The described sort of problem reminds me of the list of addresses in the back of my appointment book: there are 10 tabs for 26 first letters. Some pages are too full, others almost empty.

With an initial sort of time complexity $O(n \log n)$ and some algorithm to assign value ranges to bins I don't suppose the problem described in post #1 is necessarily $O(2^n)$ , then.

 

[Mentallic]

http://www.seas.upenn.edu/~cit596/notes/dave/p-and-np4.html

Thanks, I'll look more into integer bin packing. At the moment, my problem is going to have a value of n in the hundreds so O(2ⁿ) is just too unreasonable, but I'm confident there exists a more efficient algorithm that provides an approximate solution.

Hi guys, no solution from me, just asking for clarification: in Buzz's reference the value of the items plays a role (the integer values in each bin have to add up to the same number). It looks as if that isn't a requirement in the post #1 case. So I thought I'd just ask: would it be Ok if I would just sort the list and place the first n/k from the sorted list in bin #1, the next n/k in bin #2 etc. ?

Well, if you sort the items and place the same amount of them into each bin sequentially, you'll definitely not have a similar sum in each bin. You'll actually end up with the worst possible solution!

example, given the list, (10,5,1,2,9,5) and 2 bins, if you sort the list you'll get (1,2,5,5,9,10) and placing the first 3 into bin 1 gives 1+2+5=8 while bin 2 has 5+9+10=24. These values are the furthest from being equal to the optimal average in each bin of (1+2+5+5+9+10)/2 = 16.
Finding the optimal solution for this list can be easily done by hand since you know what the optimal solution should be, and the list is small with nice numbers that can be chosen to sum to 16.

Probably not, because that would allow items with the same value to end up in adjacent bins -- but I can't find that restriction in the description.
On the other hand: what if the list has more than k entries for items with a particular value? Would a solution have to include assigning multiple bins to the same value in such a case ? (this time I suppose a "yes"...)

In my problem, there's no issue with having many equal values. In fact, the more equal that the entire list is, the easier the problem becomes because you can choose any k values and end up with approximately the average (optimal) solution.

The described sort of problem reminds me of the list of addresses in the back of my appointment book: there are 10 tabs for 26 first letters. Some pages are too full, others almost empty.

Yes, it's very similar to that too!

 

[BvU]

Well, if you sort the items and place the same amount of them into each bin sequentially, you'll definitely not have a similar sum in each bin. You'll actually end up with the worst possible solution!

That is what I missed in the problem statement: apparently you want similar sums in each bin when you say "evenly" ?

 

[Mentallic]

That is what I missed in the problem statement: apparently you want similar sums in each bin when you say "evenly" ?

Yes.

 

[Samy_A]

Can this help?Multi-Way Number Partitioning by Richard E. Korf Computer Science Department University of California, Los Angeles.