MINIMUM 0-1 PROGRAMMING

• INSTANCE: Integer $m\times n$-matrix $A\in Z^{m\cdot n}$, integer m-vector $b\in Z^m$, nonnegative integer n-vector $c\in N^n$.

• SOLUTION: A binary n-vector $x\in \{0,1\}^n$ such that $Ax\ge b$.

• MEASURE: The scalar product of c and x, i.e., $$\sum\limits_{i=1}^{n} c_i x_i$$.

  
  

• 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 $c_i=1$ for all i is NPO PB-complete and not approximable within $n^{1-\varepsilon }$ for any $\varepsilon >0$ [284].

• Garey and Johnson: MP1