Next: MAXIMUM BOUNDED 0-1 PROGRAMMING Up: Mathematical Programming Previous: Mathematical Programming Index

### MINIMUM 0-1 PROGRAMMING

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

- 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 [236]. 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 [204].

  Variation in which ci=1 for all i is NPO PB-complete and not approximable within for any [269].

- Garey and Johnson: MP1