Timeline for Why is Savage's Vertex Cover algorithm a 2-approximation?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 4, 2022 at 18:53 | comment | added | Yuval Filmus | Which step of the proof do you think is wrong? | |
| Apr 4, 2022 at 18:52 | comment | added | Null_Space | I don't think this is right. In particular, how could you obtain the approximation factor of the original graph by only focusing on the tree? | |
| Dec 7, 2015 at 16:40 | vote | accept | oarfish | ||
| Nov 27, 2015 at 15:01 | comment | added | Yuval Filmus | I corrected the typo. | |
| Nov 27, 2015 at 15:00 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
edited body
|
| Nov 27, 2015 at 12:13 | comment | added | oarfish | How is it guaranteed that $r$ has the same number of subtrees as $r_1$? Or did you mean to write $T_1,\ldots,T_n$? | |
| Nov 26, 2015 at 21:54 | history | answered | Yuval Filmus | CC BY-SA 3.0 |