Approximation Algorithm Greedy Cut: initially,S=T=; (S,T: fori=1,2,.,n: current (S,T)in the Vi joins one of S,T beginning of i-th iteration to maximize current E(S,T); G(V,E) SOLG SOLG 1 OPTG ≥ |E1 v≥1/2of|E(S,)川+|E(T)l contributes to SOLG IEI=∑(IES,l+IET,I) E(S,T)={uv∈E|u∈S,v∈T} i=1Approximation Algorithm E(S, T) = {uv ∈ E ∣ u ∈ S, v ∈ T} Greedy Cut: initially, ; for : joins one of to maximize current ; S = T = ∅ i = 1,2,…, n vi S, T E(S, T) S T vi G(V, E) SOLG OPTG ≥ SOLG |E| , of contributes to ∀vi ≥ 1/2 |E(Si , vi )| + |E(Ti , vi )| SOLG ≥ 1 2 |E| = n ∑ i=1 (|E(Si , vi )| + |E(Ti , vi )|) : current in the beginning of -th iteration (Si , Ti ) (S, T) i