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

*Bad News:*NPO PB-complete [77].*Comment:*Transformation from LONGEST PATH WITH FORBIDDEN PAIRS. Not approximable within [279] and not within for any [285].*Garey and Johnson:*MP1