[Solved]: Bin packing with twin items

Problem Detail: 

Assume we are given $k$ bins of capacity $b$ and $n$ items with integral sizes $x_1,\dots,x_n$. The bin packing problem is to decide whether there exists an assignment of items to bins such that no bin exceeds its capacity. In this standard from, the bin packing problem is well known to be NP-hard. However, consider a version of the problem where every items has a twin of equal size. More formally, if $i$ and $j$ are twins, it holds that $x_i = x_j$.

For two bins, the problem is easy since there exists a feasible solution if and only if a packing where no twins share the same bin is feasible. However, what happens if we have more than two bins? I suspect that the problem becomes NP-hard. Unfortunately, I have not been able to prove this so far.

Does anyone have an idea for a reduction or know if the problem has been studied before? Also, if the problem is hard for twins, does the hardness carry over to triplets, quadruplets etc.?

Asked By : Dennis Kraft

Answered By : Dennis Kraft

As it turns out by a rather complicated chain of reductions starting from three dimensional matching, which is too involved to be discussed here, bin packing remains NP-hard for twin items. It even remains hard for triplets, quadruplets or any fixed number of similar items.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents