On: Solving the minimum cut problem for undirected gra...

[CountHackulus]

I remember learning an amazing randomized algorithm for max cut. If you pick edges at random 50/50 to be cut, you get a 2-approximation to the optimal solution. That is it's no more than twice as bad.

Really not bad for "just guess".

[karmakurtisaani → CountHackulus]

The first approximation algorithm, invented by Erdős. The best known by Goemans and Williamson achieves about 0.868 (IIRC) approximation, and is a thing of beauty as well.

[akoboldfrying → karmakurtisaani]

A rare example of a constant-factor approximation algorithm with a constant that's... actually useful in practice.