Correlation clustering은 그래프의 정점들을 cluster들로 분할하는데, 각 간선 eee에는 두 종류의 weight we+w_{e}^{+}we+​와 we−w_{e}^{-}we−​가 있다. 두 endpoint가 같은 cluster에 있으면 we+w_{e}^{+}we+​점, 다른 cluster에 있으면 we−w_{e}^{-}we−​점을 얻는다. 목표는 점수의 합을 최대화하는 clustering을 찾는 것이다. 이 문제는 NP-hard임이 알려져 있고, Max cut처럼 SDP를 이용한 constant factor approximation이 알려져 있다.이번에도 직관적인 0.50.50.5-approximation이 있는데, 모든 정점을 한 cluster에 놓거나 / 정점을 다 다른 cluster에 두거나 둘 중 나은 것이 최적해의 절..