patternMinor
FPT algorithm for Knapsack
Viewed 0 times
algorithmfptknapsackfor
Problem
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?
Can someone help with a reference?
Solution
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.
[1] Gurski, Frank, Carolin Rehs, and Jochen Rethmann. "Knapsack problems: A parameterized point of view." Theoretical Computer Science 775 (2019): 93-108.
Context
StackExchange Computer Science Q#142324, answer score: 3
Revisions (0)
No revisions yet.