A Faster FPTAS for Knapsack Problem With Cardinality Constraint

Wenxin Li, Joohyun Lee

We study the $K$-item knapsack problem (i.e., $1.5$-dimensional KP), which is a generalization of the famous 0-1 knapsack problem (i.e., $1$-dimensional KP) in which an upper bound…