Approximating maximum satisfiable subsystems of linear equations of bounded width

We consider the problem known as MAX-SATISFY: given a system of m linear equations over the rationals, find a maximum set of equations that can be satisfied. Let r be the width of the system, that is, the maximum number of variables in an equation. We give an Ω(m−1+1/r)-approximation algorithm for any fixed r. Previously the best approximation ratio for this problem was Ω((logm)/m) even for r=2. In addition, we slightly improve the hardness results for MAX-SATISFY.