Timeline for Minimum cover for sets in which each element appears in exactly 2 sets?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 2, 2016 at 4:09 | vote | accept | Victor Rielly | ||
| Apr 18, 2016 at 4:30 | comment | added | Victor Rielly | Ok, I got it. I looked it all up, and yeah, the two are equivalent, but as you say, they are not equivalent in terms of approximability. | |
| Apr 18, 2016 at 0:59 | comment | added | Victor Rielly | And the best solution likely scales with n? | |
| Apr 18, 2016 at 0:59 | comment | added | Victor Rielly | Can you explain the O(n^(1−ϵ)) limit to approximation? Isn't the vertex cover still going to be off by n since it is off by 2* the size of the best solution? | |
| Apr 18, 2016 at 0:10 | comment | added | Victor Rielly | Time to recheck my work. | |
| Apr 18, 2016 at 0:09 | comment | added | Victor Rielly | Woah, never mind. Apparently, unless P = NP, there is no approximation algorithm better than O(n^(1−ϵ)) | |
| Apr 17, 2016 at 23:42 | comment | added | Victor Rielly | Because I believe I have found an n^2 running time transformation from the maximum clique problem to the Vertex Cover Problem. | |
| Apr 17, 2016 at 23:30 | comment | added | Victor Rielly | Has this been proven or is this simply the best current approximation? | |
| Apr 17, 2016 at 23:13 | comment | added | Yuval Filmus | Not in terms of approximability. Vertex cover is much easier. Maximum clique cannot be approximated to within $O(n^{1-\epsilon})$. | |
| Apr 17, 2016 at 23:09 | comment | added | Victor Rielly | I believe The minimum vertex cover problem is equivalent to the maximum clique problem. | |
| Apr 17, 2016 at 22:45 | history | answered | Yuval Filmus | CC BY-SA 3.0 |