3
$\begingroup$

I tried to search whether Knapsack (the decision version) has a FPT algorithm, but didn't find anything on the topic. Can someone help with a reference?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The reference you should have found is [1], where the authors consider several parameters and also higher dimensional knapsack problems (see e.g., Table 1 for a list of running times for different parameters). A non-paywalled version is on arXiv.

[1] Gurski, Frank, Carolin Rehs, and Jochen Rethmann. "Knapsack problems: A parameterized point of view." Theoretical Computer Science 775 (2019): 93-108.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is there any parameter of the KP problem that we know that the class is not in FPT (not PFPT)? I mean, a parameter that, when considering it, KP is at least W[1]-hard. $\endgroup$
    – JoshHalas
    Jul 20, 2021 at 12:10
  • 1
    $\begingroup$ @JoshHalas According to the paper, the answer is yes if you consider the multidimensional variant of the problem. But if you insist on KP, the paper doesn't seem to give any such results. I also don't know of any such results. $\endgroup$
    – Juho
    Jul 20, 2021 at 12:17

Your Answer

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

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