News for hackers. Stuff that matters.
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.