News for hackers. Stuff that matters.
Re:Solving the minimum cut problem for undirected graphs by CountHackulus on Wednesday April 17, 2024 @02:09PM (#40068209)
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".

Re:Solving the minimum cut problem for undirected graphs by karmakurtisaani on Wednesday April 17, 2024 @02:37PM (#40068533)
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.
Re:Solving the minimum cut problem for undirected graphs by akoboldfrying on Wednesday April 17, 2024 @11:14PM (#40072614)
A rare example of a constant-factor approximation algorithm with a constant that's... actually useful in practice.