Does anyone know (or can anyone think of) a simple reduction from (for example) PARTITION, 0-1-KNAPSACK, BIN-PACKING or SUBSET-SUM (or even 3SAT) to the UBK problem (integral knapsack with unlimited number of objects of each type)? I'm writing an introduction to a few of these problems, and noticed that I hadn't really heard of a standard reduction here. Shouldn't be that hard (it's a relatively expressive problem), but I can't think of anything right now… Thoughts/references?
$\begingroup$
$\endgroup$
2
asked Sep 5, 2010 at 14:15
-
$\begingroup$ It seems that for a constant number of variables (object types), the UBK problem can be solved in polynomial time: books.google.com/books?id=u5DB7gck08YC&pg=PA211 $\endgroup$– Magnus Lie HetlandCommented Sep 5, 2010 at 14:41
-
$\begingroup$ Wikipedia gives this reference for NP-hardness: en.wikipedia.org/wiki/List_of_knapsack_problems#cite_note-0 $\endgroup$– Jukka SuomelaCommented Sep 5, 2010 at 17:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
There is a simple reduction from the subset sum problem. (We usually give it as an exercise.)
The idea is to encode in the weights that an element can only be included 0 or 1 times.
Assume the subset sum instance consists of numbers $w_1,\dots,w_n$ with target $W$. Assume that $w_i < B$ for all $i$.
We will have two new elements for each old element, simulating whether the element is used 0 or 1 times. For element $i$ we get two new weights $w^1_i = (2^{n+1} + 2^i)nB + w_i$ and $w^0_i = (2^{n+1} + 2^i)nB$. The new weight bound is defined as $W' = (n2^{n+1} + 2^n + \dots + 2^1)nB + W$. Values of elements are the same as their weights, and the target value is $W'$
answered Sep 5, 2010 at 19:33
Kristoffer Arnsfelt HansenKristoffer Arnsfelt Hansen
4,1892 gold badges27 silver badges36 bronze badges
-
$\begingroup$ Right! Very nice. I pondered some sort of binary "powers-of-two" encoding to get from the unbounded to the bounded case, actually; just didn't think it through, I guess. Thanks a lot! $\endgroup$ Commented Sep 7, 2010 at 10:47
-
1$\begingroup$ Could you please explain why we need the $n2^{n+1}$ term in each of the weights? $\endgroup$ Commented Jan 18, 2016 at 21:10
-
$\begingroup$ @user44551 I suppose, this is to make sure we do not pick more than $n$ of the elements. Observe that (a) $W'$ is less than $(n + 1) 2^{n+1} nB$ and (b) taking more than $n$ elements is a sure way to get the weight of more than that. $\endgroup$ Commented Jun 28, 2021 at 21:30
-
$\begingroup$ In fact, these terms guarantee that we take exactly $n$ elements, which, together with the bitmask thing, guarantees that we take exactly one element from each pair. $\endgroup$ Commented Jun 28, 2021 at 22:50