Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Similar to bin packing

  1. Jan 16, 2016 #1

    Mentallic

    User Avatar
    Homework Helper

    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?
     
  2. jcsd
  3. Jan 16, 2016 #2
  4. Jan 16, 2016 #3

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  5. Jan 16, 2016 #4

    Mentallic

    User Avatar
    Homework Helper

    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(2n) is just too unreasonable, but I'm confident there exists a more efficient algorithm that provides an approximate solution.

    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.

    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.

    Yes, it's very similar to that too!
     
  6. Jan 16, 2016 #5

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That is what I missed in the problem statement: apparently you want similar sums in each bin when you say "evenly" ?
     
  7. Jan 16, 2016 #6

    Mentallic

    User Avatar
    Homework Helper

    Yes.
     
  8. Jan 17, 2016 #7

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Similar to bin packing
  1. Close packing (Replies: 5)

  2. Similar Quadrilaterals (Replies: 2)

  3. Packing Problem (Replies: 11)

  4. Point packing problem (Replies: 4)

Loading...