Is this solvable in polynomial (or pseudo-polynomial) time?

Asked 2012-04-12T16:53:50.757

I'm trying to come up with a reasonable algorithm for this problem:

Let's say you have a bunch of balls. Each ball has at least one color, but can also be multicolored. Each ball has a weight and a value associated with it. There are also a bunch of boxes which are each only one color. Each box has a maximum number of balls it can hold. The goal is to maximize the sum of the value in the boxes while staying under some total weight, W, and the only rule is:

In order to place a ball in a box, it has to at least have the box's color on it

(For example, you can put a blue and green ball into a blue box or a green box, but not into a red box.)

I've dome some research and this seems similar to the knapsack problem and also similar to being solvable by the Hungarian algorithm, but I can't quite seem to reduce it to either problem.

I'm just curious is there's some kind of dynamic programming algorithm for this type of problem to make it solvable in polynomial time, or if it's just the traveling salesman problem in disguise. Would it help if I knew there were at most X colors? Any help is greatly appreciated. I could also formalize the problem a bit with variable names if it would help. Thanks!

Here's a simple example:

Maximum weight: 5

Balls:

1 red ball - (value = 5, weight = 1)

1 blue ball - (value = 3, weight = 1)

1 green/red/blue ball - (value = 2, weight = 4)

1 green/blue ball - (value = 4, weight = 1)

1 red/blue ball - (value = 1, weight = 1)

Boxes:

1 red (holds 1 ball)

1 blue (holds 2 balls)

1 green (holds 1 ball)

Optimal Solution:

red ball in red box

blue ball and red/blue ball in blue box

green/blue ball in green box

Total value: 13 (5 + 3 + 1 + 4)

Total weight: 4 (1 + 1 + 1 + 1)

Note: even though t

Edit Report

3 Answers

The reduction from knapsack is as follows. Given your knapsack instance, you create an instance of the balls and bins problem: for each item of the knapsack instance you have a ball with the same weight and value as the item. Then you have a box representing the knapsack. The balls and the box are all blue. The capacity of the box is the limit given in the knapsack problem. Given a solution to your problem, we have a set of balls in the box whose total weight is at most the knapsack limit, and whose total value is maximised.

answered 2012-04-12T17:11:10.397

This problem is NP-complete, because it subsumes the knapsack problem.

That is, it's not just similar to the knapsack problem: if there is one bowl, all the balls have that bowl's color, and the maximum number of balls in the bowl is the total number of balls, then the problem is exactly the knapsack problem.

If an algorithm could solve this problem in polynomial time, it could solve any knapsack problem in polynomial time. But, since the knapsack problem is NP-complete, this problem is, too.

answered 2012-04-12T17:16:14.207

The best you can do in this situation is get an approximation of the optimal solution - the knapsack problem is not solvable in polynomial time itself. You may be able to still get good (although not guaranteed to be optimal) results in polynomial time if you can generate a good algorithm for it.

answered 2012-04-12T17:13:07.127

Is this solvable in polynomial (or pseudo-polynomial) time?

3 Answers

Your Answer