Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR04-119 | 8th December 2004 00:00

#### On The Hardness of Approximating Max-Satisfy

TR04-119
Authors: Uriel Feige, Daniel Reichman
Publication: 21st December 2004 16:25
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