If you want to make money online : Register now

[Answers] Is ecological bin packing NP-hard?

, , No Comments
Problem Detail: 

The ACM Contest Problem 102 (HTML or PDF) can be paraphrased as:

Given 3 bins each containing possibly different number of bottles of 3 colors, move the bottles so that there is one color per bin, minimizing the number of bottle movements.

Specifically, we wish to decide on an allocation of colors to bins so that moving from the initial position to the "sorted" position requires the least number of bottle moves. The bins are assumed to have infinite capacity.

For the problem as stated, one can brute-force check all $3! = 6$ permutations to see which has the fewest number of bottle movements. However, for $N > 3$ colors of glass, $N!$ grows very large. Is there a way to solve this problem for general $N$ that runs in polynomial time?

Asked By : cm007

Answered By : D.W.

Yes, this can be solved in polynomial time, for arbitrary $N$. This is an instance of the assignment problem, for which polynomial-time algorithms are known.

You want to assign a color of glass to each bin, such that each bin gets exactly one color, and each color is assigned to exactly one bin. The cost of assigning bin $b$ to color $c$ is the number of bottle moves needed to move all bottles of color $c$ that aren't currently in bin $b$, into bin $b$. Therefore, this is an assignment problem.

(You can compute this cost function more efficiently as follows: the cost of assigning bin $b$ to color $c$ is the number of moves needed to move all bottles that aren't colour $c$ out of bin $b$. Thanks to @David Richerby for this insight.)

The assignment problem can be solved using standard methods, e.g., the Hungarian algorithm or algorithms for min cost max flow.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32332

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback