Next: MAXIMUM PACKING INTEGER PROGRAMMING Up: Mathematical Programming Previous: MINIMUM 0-1 PROGRAMMING Index

### MAXIMUM BOUNDED 0-1 PROGRAMMING

- INSTANCE: Integer m x n-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 [71].

- Comment: Transformation from LONGEST PATH WITH FORBIDDEN PAIRS. Not approximable within [264] and not within for any [270].

- Garey and Johnson: MP1