Next: MAXIMUM INTEGER K-CHOICE KNAPSACK
Up: Mathematical Programming
Previous: MAXIMUM KNAPSACK
  Index
- 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
Viggo Kann
1999-04-22