2
$\begingroup$

Consider the following traditional integer knapsack problem:

$\max \sum_{i=1}^k p_i \cdot x_i\\ \text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\ x_i \in \{0,\ldots,k_i\} \text{ for each } i$

Now consider a laminar family $\mathcal{I}$ of sets, i.e., a collection of subsets of $\{1,\ldots,k\}$ such that for each pair $I_1,I_2 \in \mathcal{I}$ it either holds that $I_1 \subseteq I_2$ or $I_1 \supseteq I_2$ or $I_1 \cap I_2 = \emptyset$. For each of these subsets $I_j \in \mathcal{I}$, we insert an additional cardinality constraint of the form

$\sum_{i \in I_j} x_i \leq \mu_j$

for some number $\mu_j$.

Clearly, this problem is weakly $NP$-complete in general since it contains the traditional (integer) knapsack problem. The question is what happens if the profits $p_i$ are polynomially bounded. Does the problem remain $NP$-complete or is it easy to solve now? We are thinking about this problem for months now.

What we know so far:

  • If we omit the cardinality constraints or restrict ourselves to only one cardinality constraint that involves each of the variables, the problem becomes easy to solve (this isn't as trivial as it sounds since the maximum amounts $k_i$ are still not polynomially bounded).
  • Accordingly, if the maximum amounts $k_i$ are polynomially bounded, the problem becomes easy to solve as well.

The above results imply that, in order to prove $NP$-completeness, a possible reduction would need to make use of decision variables that are not polynomially bounded and must incorporate suitable laminar cardinality constraints with values $\mu_j$ that aren't polynomially bounded as well.

So, does anyone have some clue on how to prove or disprove the $NP$-completeness of the problem?

$\endgroup$
-1
$\begingroup$

It can be solved by a similar DP for traditional knapsack problem, and thus still weak NP-complete. In the following we assume that the subsets $I_j$ are mutually disjoint, and the other case (some subsets are super sets of others) is similar.

In the DP algorithm for knapsack, let $T[p,i]$ be the minimum weight to reach profit $p$ by only using the first $i$ items. Now arrange the items such that all items in the same $I_j$ are consecutive. Since $I_j$ are disjoint, when dealing with $x_i$, we only need to consider how many items in $I_j$ can be picked. Thus, for each $p$ and $i$, let $D[p,i,q]$ be the minimum weight to reach profit $p$ by only using the first $i$ items and using only $q$ items in $I_j$. The table size is bounded by $P\times n^2$, where $n$ is the number of items and $P$ is the maximum profit. Since you assume that $P$ is polynomial, it takes polynomial time.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Unfortunately, I must disagree. Since we are dealing with an integer knapsack problem rather than the traditional 0/1-knapsack problem, the table size is bounded by $P \cdot n \cdot (n \cdot K)$, where $K := \max_i k_i$. Note that nethier $K$, nor $P$ are polynomially bounded. Your suggested DP only works in polynomial time if $K$ is polynomially bounded as well, as noted in my second remark above. $\endgroup$ – user1742364 Jan 8 '15 at 9:11
  • $\begingroup$ OK, sorry I did not notice that. It seems to me your question is more difficult than the usual questions in this forum. Maybe you can try to ask it in Theoretic Computer Science of StackExchange. $\endgroup$ – Bangye Jan 8 '15 at 12:18
  • $\begingroup$ @Bangye, Any chance you have a look at this - math.stackexchange.com/questions/2415617? Thank You. $\endgroup$ – Royi Sep 3 '17 at 21:10

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.