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

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?

• MOST is a vague term. And you said m=n is valid. Oct 16 '18 at 17:25
• @kelalaka yes I specified a little more. Thanks. Yes m = n is a valid but not a necessity; if m = n thats great but if m < n that's fine as long as m is the largest number of solvable equations in the system Oct 16 '18 at 17:40
• I’m assuming everything is done mid 2. In this case, it is NP-hard to approximate better than a factor 2 (which you can get from a random assignment) even if each equation involves only three variables, a problem known as 3LIN, Oct 16 '18 at 20:45
• Your example does not help to understand the question (at least to me). I suggest to remove the "example" part. Oct 17 '18 at 3:54
• @YuvalFilmus THis has definitely helped; Thank you. 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? Oct 17 '18 at 19:09

$$\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.
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.