Advanced Algorithms SDP-Based Algorithms 尹一通Nanjing University,2022Fall
尹⼀通 Nanjing University, 2022 Fall Advanced Algorithms SDP-Based Algorithms
Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of Vinto S and Ithat maximizes the cut E(S,T)={w,v}∈E|w∈S∧v∈T}. NP-hard. One of Karp's 21 NP-complete problems(reduction from the Partition problem). a typical Max-CSP(Constraint Satisfaction Problem). Greedy is 1/2-approximate. Local search is 1/2-approximate
Max-Cut 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} T S • NP-hard. • One of Karp’s 21 NP-complete problems (reduction from the Partition problem). • a typical Max-CSP (Constraint Satisfaction Problem). • Greedy is 1/2-approximate. • Local search is 1/2-approximate
Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of Vinto S and Ithat maximizes the cut E(S,T)={w,v}∈E|w∈S∧v∈T}. max Yuv uv∈E not linear S.t. yuu≤lEu-xul, Vuw∈E xu∈{0,1， Vu∈V
Max-Cut 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} T S max X uv2E yuv s.t. yuv |xu xv|, xv 2 {0, 1}, 8uv 2 E 8v 2 V not linear
Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of V into S and I that maximizes the cut E(S,T)={u,v}∈E|u∈S∧v∈T. max Yuv uw∈E s.t. yuv≤yuw+ywv, ,v,w∈V yuw+yuw+yu≤2，u,v,2w∈V yuw∈{0,1}， u,v∈V u,y,w∈V:0or2of{u,y以，{y,w以，{u,w} are“crossing pairs
Max-Cut 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} T S max X uv2E yuv s.t. yuv 2 {0, 1}, yuv yuw + ywv, yuv + yuw + ywv 2, 8u, v, w 2 V 8u, v, w 2 V 8u, v 2 V ∀u,v,w ∈ V: 0 or 2 of {u,v}, {v,w}, {u,w} are “crossing pairs
Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of V into S and I that maximizes the cut E(S,T)={w,v}∈E|uw∈S∧v∈T}. max ∑aw integrality gap≥2 uw∈E S.t.yuw≤yuw+yww, u,v,w∈V 人 yuw+yuw+ywu≤2，，v,w∈V yuv∈{0,1}， u,v∈V V8>0:3G s.t.OPTLP(G)/OPTIP(G)>2-8
Max-Cut 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} T S max X uv2E yuv s.t. yuv 2 {0, 1}, yuv yuw + ywv, yuv + yuw + ywv 2, 8u, v, w 2 V 8u, v, w 2 V 8u, v 2 V integrality gap ≥ 2 ∀ε>0: ∃G s.t. OPTLP(G)/OPTIP(G) > 2-ε