Take a star with many (>3) leaves
Replace every leaf by a star
The algorithm fails by picking up leaves
I remember proving this algorithm in class (a while ago). What I found interesting from Wikipedia is that this is the best known approximation, there is a proven lower bound of 1.363.
Most likely I’m not understanding the problem, would appreciate if someone could clarify.
So in the simplest case of two vertices connected by an edge, your algorithm would generate a set of size 2 instead of the minimum size 1.
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.
Given a set of clauses C_1 ^ C_2 ^ ... ^ C_n where each clause is an OR of 3 logical variables, find assignments to each variable to maximize the number of clauses satisfied.
The algorithm is to just assign each variable randomly. For each clause, there are 8 possible assignments, and 7 out of 8 make the clause true. Therefore, randomly assigning them gives you a 7/8-approximation.
What makes this so fascinating to me is that the difference between a (polynomial) algorithm that gets 7/8 right and one that gets 8/8 right is the difference between a child randomly guessing and solving all of the world's most important problems in a single algorithm. It could be worth trillions of dollars. Of course, it's probably impossible and therefore P != NP.
