News for hackers. Stuff that matters.

A comment on The World's Simplest Interesting Algorithm (2019).

Re:The World's Simplest Interesting Algorithm (2019) by lalaland1125 on Wednesday June 10, 2020 @01:52AM (#23474367)
The proof here is incorrect. The issue is that it doesn't establish that the number of edges processed is less than or equal to the size of the optimal vertex cover. This is critical and has to do with the fact that we only process edges that aren't already covered.

https://www.cl.cam.ac.uk/teaching/1415/AdvAlgo/lec8_ann.pdf contains a more correct proof.

Note the |C∗| ≥ |A| line on slide 8. That's critical to the correctness of the proof, but missing in this article.

[ Parent | on HN ]
Re:The World's Simplest Interesting Algorithm (2019) by saagarjha on Wednesday June 10, 2020 @02:00AM (#23474397)
The proof here is not incorrect; it does not make any claims on performance. Usually you’d care that your algorithm is not exponential, but here the claim was that this algorithm provides some approximation that is within a constant factor of the optimal solution in terms of the number of vertices it picks.
[ Parent | on HN ]