MINIMUM UNSATISFYING LINEAR SUBSYSTEM

• INSTANCE: System Ax=b of linear equations, where A is an integer $m\times n$-matrix, and b is an integer m-vector.

• SOLUTION: A rational n-vector $x\in Q^n$.

• MEASURE: The number of equations that are not satisfied by x.

  
  

• Bad News: Not in APX [35].

• Comment: Not approximable within $2^{\log^{1-\varepsilon } n}$ for any $\varepsilon >0$ unless NP$\subset$QP [35]. If the system consists of relations (> or $\ge$) the problem is even harder to approximate; there is a transformation from MINIMUM DOMINATING SET to this problem. If the variables are restricted to assume only binary values the problem is NPO PB-complete both for equations and relations, and is not approximable within $n^{1-\varepsilon }$ for any $\varepsilon >0$. Approximability results for even more variants of the problem can be found in [17].