- INSTANCE:
Integer -matrix
,
integer
*m*-vector , nonnegative integer*n*-vector . - SOLUTION:
A binary
*n*-vector such that . - MEASURE:
The scalar product of
*c*and*x*, i.e., .

*Bad News:*NPO-complete [388].*Comment:*Transformation from MINIMUM WEIGHTED SATISFIABILITY. Variation in which there are at most 3 non-zero entries on each row of the matrix is still NPO-complete [Klauck, --], but if there are at most 2 non-zero entries on each row it is approximable within 2 [253]. If all entries of*A*are non-negative, and there are at most*k*non-zero entries on each row with*k*constant, the problem is approximable within*k*[217].Variation in which for all

*i*is NPO PB-complete and not approximable within for any [284].*Garey and Johnson:*MP1