Local Search Local Search: initially,(S,T)is an arbitrary cut; repeat until nothing changed: ifv switching side increases cut v switches to the other side; in a local optima: v∈S:|E(y,S)川≤|E(y,T)川→21E(S,S)川≤|E(S,T)川 v∈T:|E(y,T)川≤IE(y,S)l→2|E(T,T)川≤IE(S,T)l E(S,S)+E(T,T)<E(S,T) OPT≤IE1=IE(S,S)川+IE(T,T)川+IE(S,T)I≤2|E(S,T)I →IE(S,T)I≥二OPTLocal Search Local Search: initially, is an arbitrary cut; repeat until nothing changed: if switching side increases cut switches to the other side; (S, T) ∃v v in a local optima: ∀v ∈ S : |E(v, S)| ≤ |E(v, T)| ⟹ 2|E(S, S)| ≤ |E(S, T)| ∀v ∈ T : |E(v, T)| ≤ |E(v, S)| ⟹ 2|E(T, T)| ≤ |E(S, T)| |E(S, S)| + |E(T, T)| ≤ |E(S, T)| OPT ≤ |E| = |E(S, S)| + |E(T, T)| + |E(S, T)| ⟹ |E(S, T)| ≥ 1 2 OPT ≤ 2|E(S, T)| T S