MAXIMUM INTEGER K-CHOICE KNAPSACK

• INSTANCE: Nonnegative integer $n\times k$-matrices $A,C\in N^{n\cdot k}$, nonnegative integer $b\in N$.

• SOLUTION: Nonnegative integer vector $x\in N^n$, function $f: [1..n]\rightarrow [1..k]$ such that $$\sum\limits_{i=1}^{n} a_{i,f(i)} x_i\le b$$.

• MEASURE: $$\sum\limits_{i=1}^{n} c_{i,f(i)} x_i$$.

  
  

• Good News: Admits an FPTAS [97].

• Comment: The corresponding minimization problem, where $\sum\limits_{i=1}^{n} a_{i,f(i)} x_i\ge b$ also admits an FPTAS as well as the variation in which there does not need to be a chosen element for each i [191].

• Garey and Johnson: Similar to MP11