MAXIMUM BOUNDED 0-1 PROGRAMMING

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

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

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

  
  

• Bad News: NPO PB-complete [77].

• Comment: Transformation from LONGEST PATH WITH FORBIDDEN PAIRS. Not approximable within $n^{1-\varepsilon }$ [279] and not within $m^{1-\varepsilon }$ for any $\varepsilon >0$ [285].

• Garey and Johnson: MP1