On the hardness of approximating Max-Satisfy
Max-Satisfy is the problem of finding an assignment that satisfies the maximum number of equations in a system of linear equations over Q. We prove that unless NP subset of BPP Max-Satisfy cannot be efficiently approximated within an approximation ratio of 1/1n(1-epsilon), if we consider systems of n linear equations with at most n variables and epsilon > 0 is an arbitrarily small constant. Previously, it was known that the problem is NP-hard to approximate within a ratio of 1/n(alpha), but 0 < alpha < 1 was some specific constant that could not be taken to be arbitrarily close to 1. (c) 2005 Elsevier B.V. All rights reserved.
approximation algorithms computational complexity