Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-119 | 8th December 2004 00:00

On The Hardness of Approximating Max-Satisfy

RSS-Feed




TR04-119
Authors: Uriel Feige, Daniel Reichman
Publication: 21st December 2004 16:25
Downloads: 1187
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint