MAXIMUM INTEGER M-DIMENSIONAL KNAPSACK

• INSTANCE: Nonnegative integer $m\times n$-matrix, $A\in N^{m\cdot n}$, nonnegative integer m-vector $b\in N^m$, nonnegative integer n-vector $c\in N^n$. m is a constant, $m\in Z^+$.

• SOLUTION: Nonnegative integer n-vector $x\in N^n$ such that $Ax\le b$.

• MEASURE: The scalar product of c and x, i.e., $$\sum\limits_{i=1}^{n} c_i x_i$$.

  
  

• Good News: Admits a PTAS [97].

• Garey and Johnson: Generalization of MP10