Re:First improvement of fundamental algorithm in 10 years
by JosefK on Tuesday September 28, 2010 @12:41PM
(#1736240)
I believe you mean Max-Cut can be 2 approximated with the trivial random algorithm. Min cut can be solved exactly, and that algorithm would give an expected n^2 approx factor (for min cut).
This is a common thing to use in randomized or approximate algorithms. For example, solving min-cut by assigning to 2 sets randomly is provably a 2-approximation.