HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

FPT algorithm for Knapsack

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#142324, answer score: 3

Revisions (0)

No revisions yet.