Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

Question

My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a solution set that solves the entire set of equations. It only needs to solve the MOST number of these equations. For example, if a given linear system has $n$ equations, then the solution set returned by the algorithm should "fit" the most possible number of equations in the system.

Example: if there are $N$ linear equations in a system $S$ of linear equations, then the algorithm should return a solution set that solves $m$ linear equations in $S$, where $m\le N$.

Based on what I have researched, none of the algorithms I know of will do this. Hopefully I am just missing something and I can get pointed into the right direction. Thanks.

Also, I forgot to add in that the given system of equations will have 10,000-1,000,000 variables, with x being Sparse. Is there a mod 2 algorithm or something similar to it that works on very large matricies?

Answer 1

$\mathsf{3LIN}$ is the following problem:

Given a set of linear equations of the form $x_i \oplus x_j \oplus x_k = b$, where $1 \leq i,j,k \leq n$ and $b$ is a bit, find an assignment for the bits $x_1,\ldots,x_n$ that satisfies the largest number of equations.

There is a simple 1/2-approximation algorithm, which simply chooses a random assignment. Such an assignment satisfies half of the equations in expectation, and so at least 1/2 of the optimum. Using the method of conditional expectations, it is routine to derandomize this algorithm.

Håstad, in his paper Some optimal inapproximability results, showed that it is NP-hard to approximate 3LIN to within $1/2+\epsilon$ for any $\epsilon > 0$. In other words, the trivial algorithm mentioned above gives the optimal approximation ratio.