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