patternMinor
Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?
Viewed 0 times
canthesolutionnumberequationslinearsystemalgorithmthatfind
Problem
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?
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?
Solution
$\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.
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.
Context
StackExchange Computer Science Q#98684, answer score: 3
Revisions (0)
No revisions yet.