Algorithm Question

So I’ve been puzzling over a scenario all day. (This is not a homework problem, but is a generalization of a real world scenario). Not sure if this should go in GQ or IMHO, so feel free to move

I’ve got some buckets to put some balls in. Each bucket has some rules, eg “This bucket is for green balls marked with a number between 0 and 7. You can put 6 balls in this bucket”. Another bucket might say “This bucket is for green and red balls. You can put 4 balls in this bucket.” (Every bucket has a maximum number of balls, but may have different characteristics for other rules).

The object is to put as many balls as possible into the buckets. Right now I’m dealing with ~5k balls and ~400 buckets.

How would you approach this problem?

My approach is to determine which balls could go in the least possible buckets, sort them that way and then put them into the least full bucket by pct of filled. This approach has some holes in it however.

It depends on how complicated the rules can be. With numbered balls and a rule like “The sum of the numbers of the balls in this bucket can be at most x.”, then you have a bin packing problem which is NP-hard.

If the rules are solely “unitary” in some sense, each ball counts as one, then the problem is poly time and can be solved using dynamic programming. (Also assuming that there is no linkage between buckets. I.e., no “The bucket on the left of this one has to have fewer balls.”) I get an upper bound of O(number of buckets[sup]2[/sup] x number of balls) with some chance of significant improvement if the order of buckets doesn’t matter.

O(buckets…)? Hmmm. I don’t see that.

I think the buckets are a distraction, given the problem statement. Instead of worrying about buckets, worry about slots: E.g. for red/green bucket with a capacity of four what you really have is four separate red/green slots.

Imagine a graph connecting every ball with every slot permitted slot. This is a bipartite graph, as there aren’t edges among balls or slots. You now want a maximum matching of this graph. http://en.wikipedia.org/wiki/Bipartite_matching#Maximum_matchings_in_bipartite_graphs

[oops, I left out a bit I intended to add]

For the problem size you’re suggesting, I don’t see any reason why you couldn’t find an optimal solution … a few tens of billions of operations isn’t too much for computers today. :wink: An optimal solution has the benefit of being… optimal. :wink:

If you’re willing to tolerate an non-optimal solution or if your problem has conditions that break the bipartie graph representation that I’ve suggested (and the reasonably fast solutions for it, like Hopcroft-Karp), you could just throw an integer constraint satisfier at it. I’m a fan of the minion software package: http://minion.sourceforge.net/

Right now the amount of a ball you put in a bucket is in {0, 1}, but if you could relax that to [0, 1], would you have a linear program? If so, you can solve that linear program and then use randomized rounding or some other LP -> ZOIP approximation routine.