The Simplest Interesting Algorithm (2019)(algorithmsoup.wordpress.com)

2 pointsby randomizedalgsvor 5 Jahren2 comments

algorithmsoup.wordpress.com

The Simplest Interesting Algorithm (2019)

https://algorithmsoup.wordpress.com/2019/10/25/the-worlds-simplest-interesting-algorithm/

2 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.

anikan_vadervor 5 Jahren

I refer you to Bogosort. [1] One of the simplest interesting randomized algorithms.

https://en.wikipedia.org/wiki/Bogosort