오늘 다룰 Max Cut 문제는 non-negative weighted undirected graph G=(V,E,w)G = (V, E, w)G=(V,E,w)에 대해서 S⊆VS \subseteq VS⊆V를 골라서 vE(S,V−S)vE(S, V - S)vE(S,V−S)의 weight 합을 최대화하는 문제이다. 다항 시간 알고리즘이 알려진 min cut에 비해 이 문제는 NP-hard임이 알려져 있다.NP-hard problem의 경우 여러 근사 알고리즘들이 존재하는데, 가장 naive한 알고리즘부터 생각해보자. 임의의 S⊆VS \subseteq VS⊆V에 대해 E(S,V−S)E(S, V-S)E(S,V−S)의 weight 합, 즉 ∑e∈E(S,V−S)w(e)\sum_{e \in E(S, V-S)} w(e)∑e∈E(S,V−S)​w(e)를 w(∂S)w(\partial S)w(∂S)라고 표기하자. w(∂S)w(\partial S)w(∂S)의 가능한 최댓값, 즉 MAX CUT을 $\mat..