The randomized version of this algorithm is also fun: repeatedly find an edge that is not yet covered, select one of the two end points at random, and add it to S.
It's a nice exercise to show that the randomized algorithm is also a 2-approximate algorithm, i.e., the size of S is at most twice the size of S_{OPT}, in expectation.
Comments
The randomized version of this algorithm is also fun: repeatedly find an edge that is not yet covered, select one of the two end points at random, and add it to S.
It's a nice exercise to show that the randomized algorithm is also a 2-approximate algorithm, i.e., the size of S is at most twice the size of S_{OPT}, in expectation.