MAXIMUM SATISFYING 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 satisfied by x.

  
  

• Good News: Approximable within $O(m/\log m)$ [223].

• Bad News: Not approximable within $m^{\varepsilon }$ for some $\varepsilon >0$ [16] and [35].

• Comment: For any prime $q\ge 2$ the problem over GF[q] is approximable within q, but is not approximable within $q-\varepsilon$ for any $\varepsilon >0$, even if the number of variables in each equation is exactly three. When there are at most two variables in each equation the problem over GF[2] is approximable within 1.383 but is not approximable within 1.0909 [242]; not approximable within 1.0030 if the number of occurrences of any variable is bounded by 3 [76]. When there are at most two variables in each equation the problem over GF[q] for any prime $q\ge 2$ is approximable within $q-\delta$ for some $\delta>0$ (dependent on q) but not approximable within 70/69$-\varepsilon$ for any $\varepsilon >0$ [22]. When there are exactly k variables in each equation and the number of equations is $\Theta(n^k)$ the problem over GF[q] for any prime $q\ge 2$ admits a randomized PTAS [21].

  The variation in which the system consists of relations (> or $\ge$) is APX-complete and approximable within 2 [16]. If the variables are restricted to assume only binary values, the problem is harder to approximate than MAXIMUM INDEPENDENT SET. Approximability results for even more variants of the problem can be found in [16].