Proving bounds for the Randomized MaxCut Approximation algorithm in Lean4
12 points by aphaelion
12 points by aphaelion
I stared for quite a while at this paragraph, and how it relates to the later use of the term "1/2-approximation":
Some quick nomenclature: an α-approximation for a (maximization/minimization) problem is when we:
(max) Do as good as 1/α * OPT (min) Do as good as α * OPT
soo... a 1/2-approximation of maxcut would have the size of 1/(1/2) * OPT = 2 * OPT? I think you might have inverted the two lines by accident?
Either way, interesting article!
Good catch lol, I think the terminology can be pretty ambiguous; the α is usually gleaned from context, and thus saying 1/2-approximation is similarly common.
For context, I lifted that definition from my course notes, and of the two articles I linked at the top, one uses 1/2-approx and the other uses 2-approx.
Glad you enjoyed!