Timeline for Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 24, 2018 at 22:29 | vote | accept | mathwizzz22 | ||
| Oct 17, 2018 at 19:10 | history | edited | mathwizzz22 | CC BY-SA 4.0 |
added in more information about the problem
|
| Oct 17, 2018 at 19:09 | comment | added | mathwizzz22 | @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, 2018 at 12:00 | history | tweeted | twitter.com/StackCompSci/status/1052529772872503296 | ||
| Oct 17, 2018 at 4:01 | answer | added | Yuval Filmus | timeline score: 3 | |
| Oct 17, 2018 at 3:54 | comment | added | xskxzr | Your example does not help to understand the question (at least to me). I suggest to remove the "example" part. | |
| Oct 17, 2018 at 3:52 | history | edited | xskxzr | CC BY-SA 4.0 |
deleted 8 characters in body
|
| Oct 16, 2018 at 20:45 | comment | added | Yuval Filmus | 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, 2018 at 19:01 | history | edited | mathwizzz22 | CC BY-SA 4.0 |
edited body
|
| Oct 16, 2018 at 17:40 | comment | added | mathwizzz22 | @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, 2018 at 17:39 | history | edited | mathwizzz22 | CC BY-SA 4.0 |
added 169 characters in body
|
| Oct 16, 2018 at 17:25 | comment | added | kelalaka | MOST is a vague term. And you said m=n is valid. | |
| Oct 16, 2018 at 17:15 | review | First posts | |||
| Oct 17, 2018 at 11:15 | |||||
| Oct 16, 2018 at 17:13 | history | asked | mathwizzz22 | CC BY-SA 4.0 |