4 ms·
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.
by CountHackulus 2y ago
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 2y agoThe 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 2y agoA rare example of a constant-factor approximation algorithm with a constant that's... actually useful in practice.