3
$\begingroup$

Say that we have some (integer) weights $w_{1,1},w_{1,2},...,,w_{m,m}$ and a target sum $W$.

Suppose that we want to find whether there are $a_1,...,a_m \in \{0,1\}$ such that

$$\sum_{i = 1}^{m} \sum_{j = i}^m a_i a_j w_{i,j} = W.$$

I read through the Wikipedia article on the quadratic knapsack problem. It mentions (but does not completely spell out why) that pseudo polynomial dynamic programming algorithms can only function as a heuristic for the QKP.

Has it been shown that there is no pseudo polynomial time algorithm for this 0-1 quadratic subset sum problem under reasonable assumptions?

Improve this question
$\endgroup$
2
  • $\begingroup$ It might be worthwhile to look through the literature on the quadratic knapsack problem to see if it addresses this variant of the problem. The first citation in the first paragraph of the Wikipedia article on the quadratic knapsack problem mentions that on its second page that the quadratic knapsack problem is as hard as the clique problem and thus is NP-hard (and Wikipedia also says the problem is NP-hard). (continued) $\endgroup$
    – D.W. ♦
    Sep 5, 2017 at 21:07
  • $\begingroup$ I don't see how to apply that to your special case of the quadratic knapsack problem, but you might try adapting that reduction (e.g., set $w$ to be the adjacency matrix of the graph or something similar, etc.). You could also take a look at other graph problems to see if you can find any that seem like plausible reduction partners. $\endgroup$
    – D.W. ♦
    Sep 5, 2017 at 21:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.