MAXIMUM INTEGER K-CHOICE KNAPSACK

Next: MAXIMUM CLASS-CONSTRAINED KNAPSACK Up: Mathematical Programming Previous: MAXIMUM INTEGER M-DIMENSIONAL KNAPSACK Index

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 $\displaystyle\sum\limits_{i=1}^{n} a_{i,f(i)} x_i\le b$ .
MEASURE: $\displaystyle\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

Viggo Kann
2000-03-20