4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ MOST is a vague term. And you said m=n is valid. $\endgroup$ – kelalaka Oct 16 '18 at 17:25
  • $\begingroup$ @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 $\endgroup$ – mathwizzz22 Oct 16 '18 at 17:40
  • 2
    $\begingroup$ 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, $\endgroup$ – Yuval Filmus Oct 16 '18 at 20:45
  • $\begingroup$ Your example does not help to understand the question (at least to me). I suggest to remove the "example" part. $\endgroup$ – xskxzr Oct 17 '18 at 3:54
  • $\begingroup$ @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? $\endgroup$ – mathwizzz22 Oct 17 '18 at 19:09
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.