2
$\begingroup$

Under Multidimensional knapsack STRONGLY NP-complete it was discussed that the Multidimensional Knapsack problem is strongly NP-hard.

Within this discussion the question whether the problem is W[1]-hard when parameterized by dimension d was mentioned, but not finally answered. Is the problem solved?

And: Is there any known xp-algorithm for multidimensional knapsack w.r.t. parameter dimension?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Sure the problem is at least W[1]-hard (unless P=NP). Because Knapsak is already NP-Complete. $\endgroup$ – Saeed Apr 19 '14 at 14:46

Your Answer

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

Browse other questions tagged or ask your own question.