Approximation Ratio Algorithm & Instance G: Greedy Cut: initially,S=T=O; fori=1,2,.,n: Vi joins one of S,T to maximize current E(S,T); OPTG:value of max-cut in G SOLG:value of the cut returned by on G Algorithm has approximation ratio a if SOLG V instance G, ≥ OPTGApproximation Ratio Greedy Cut: initially, ; for : joins one of to maximize current ; S = T = ∅ i = 1,2,…, n vi S, T E(S, T) Algorithm 𝒜: Instance G: : value of max-cut in : value of the cut returned by on OPTG G SOLG 𝒜 G Algorithm has approximation ratio if instance , 𝒜 α ∀ G SOLG OPTG ≥ α