Local Search Instance:An undirected graph G(V,E). Solution:A bipartition of V into S and T that maximizes the cut E(S,T)={w,v}∈Eluw∈S∧v∈T}. Local Search: initially,(S,T)is an arbitrary cut; repeat until nothing changed: if v switching side increases cut v switches to the other side; locally improve the solution until no improvement can be made (local optima,fixpoint)Local Search Instance: An undirected graph . Solution: A bipartition of into and that maximizes the cut . G(V, E) V S T E(S, T) = {{u, v} ∈ E ∣ u ∈ S ∧ v ∈ T} 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 locally improve the solution until no improvement can be made (local optima, fixpoint) T S