5 ms·
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
by randomizedalgs 5y ago
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.