TR04-119 Authors: Uriel Feige, Daniel Reichman

Publication: 21st December 2004 16:25

Downloads: 3002

Keywords:

Max-Satisfy is the problem of finding an assignment that satisfies

the maximum number of equations in a system of linear equations

over $\mathbb{Q}$. We prove that unless NP$\subseteq $BPP there is no

polynomial time algorithm for the problem achieving an

approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number

of equations in the system 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.