Next: MAXIMUM INTEGER K-CHOICE KNAPSACK Up: Mathematical Programming Previous: MAXIMUM KNAPSACK Index

### MAXIMUM INTEGER M-DIMENSIONAL KNAPSACK

- INSTANCE: Nonnegative integer m x n-matrix, , nonnegative integer m-vector , nonnegative integer n-vector . m is a constant, .

- SOLUTION: Nonnegative integer n-vector such that .

- MEASURE: The scalar product of c and x, i.e., .

- Good News: Admits a PTAS [89].

- Garey and Johnson: Generalization of MP10