6
$\begingroup$

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.?

$\endgroup$
2
  • $\begingroup$ One obvious approach is: Given a instance of bin packing, create an instance of twinned bin packing by cloning (twinning) all the items and cloning (twinning) all of the bins. However, this doesn't work. If there's a solution to the original bin packing problem, there'll be a solution to the derived twinned bin packing problem... but the converse doesn't hold. Just documenting something that doesn't work. $\endgroup$
    – D.W. ♦
    Aug 25, 2015 at 16:43
  • 1
    $\begingroup$ @D.W. you are correct. Although I found it somewhat tricky to find an example, where the normal bin packing instance has no solution but the twin version does. Take for instance 6 bins of capacity 27 and 18 items with sizes 1, 1, 1, 3, 3, 5, 7, 7, 9, 9, 9, 9, 9, 13, 13, 19, 21, 23. It is easy to verify that there is no feasible packing. However, if we have twice the number of bins and every item has a twin, then there is a feasible solution, namely [23, 3, 1], [23, 3, 1], [21, 3, 3], [21, 5, 1], [19, 7, 1], [19, 7, 1], [13, 13, 1], [13, 7, 7], [13, 9, 5], [9, 9, 9], [9, 9, 9], [9, 9, 9]. $\endgroup$
    – Dennis Kraft
    Aug 26, 2015 at 13:38

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ This conveys very little information. Can you at least give a citation? $\endgroup$
    – David Richerby
    Sep 24, 2015 at 10:07
  • $\begingroup$ @DavidRicherby I will add one once it is finished. But since it is not straight forward, it might take some time to write it up. I just wanted to share the current state of the problem before someone else wracks their brain ;) $\endgroup$
    – Dennis Kraft
    Sep 24, 2015 at 10:28
  • $\begingroup$ Fair enough -- I'd not realised it was a work in progress rather than something you'd found somewhere. $\endgroup$
    – David Richerby
    Sep 24, 2015 at 10:30
  • $\begingroup$ @DennisKraft did you write up your solution? $\endgroup$
    – user108903
    Sep 8, 2019 at 13:21
  • $\begingroup$ xkcd.com/1381 $\endgroup$
    – Erel Segal-Halevi
    Feb 17, 2021 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.