Next: MAXIMUM INTEGER M-DIMENSIONAL KNAPSACK
Up: Mathematical Programming
Previous: MAXIMUM HYPERPLANE CONSISTENCY
  Index
- INSTANCE:
Finite set U, for each
a size
and a value
,
a positive integer
.
- SOLUTION:
A subset
such that
.
- MEASURE:
Total weight of the chosen elements, i.e.,
.
- Good News:
Admits an FPTAS [266].
- Comment:
The special case when s(u)=v(u) for all
is called
MAXIMUM SUBSET SUM.
The corresponding minimization problem where
also admits an FPTAS, as well as
several other variations of the knapsack problem [191].
- Garey and Johnson: MP9
Viggo Kann
2000-03-20