Approximating maximum satisfiable subsystems of linear equations of bounded width
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 Omega(m(-1+1/r))-approximation algorithm for any fixed r. Previously the best approximation ratio for this problem was Omega((log m)/m) even for r = 2. In addition, we slightly improve the hardness results for MAX-SATISFY. (c) 2007 Elsevier B.V. All rights reserved.
linear equations satisfiable systems approximation algorithms