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

https://www.acmicpc.net/problem/25510https://infossm.github.io/blog/2022/08/18/CharPoly/Division-Free Determinant에 대해 위 문제를 내고 글도 썼는데, 최근 훨씬 간단한 알고리즘이 있다고 해서 정리해보려고 한다.원본 글에 달린 것과 동일하게 $\mathcal{O}(n^4)$에 동작하는 division-free characteristic polynomial 알고리즘이다.Algorithm$n \times n$ 행렬 $A = (a_{ij})$에 대해, $A_{i}$를 $i\dots n$번째 행, 열만 따와서 만든 크기 $n-i+1$의 정사각행렬이라고 하자. 당연히 $A_{1} = A$이다.$p_{1}(x) = \det(x..

오늘 다룰 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..

Bostan-Mori algorithm흔히 "선형 점화식의 $N$번째 항"을 구하는 알고리즘으로 알려진 방법이다. 사실은 보다 일반적으로, $P(x)/Q(x)$ 꼴의 rational power series의 $N$차항 계수를 구하는 데 사용할 수 있다.Theorem. $\deg P 어떤 다항식 / power-series의 $N$차항 계수를 $[x^N]f(x)$로 쓴다.$\mathcal{M}(d)$는 $\mathbb{F}[x]$의 두 $d$차 다항식을 곱하는 데 걸리는 시간이다. Computer algebra에서는 sublogarithmic factor를 따지지만, PS 범위에서는 $\mathcal{M}(d) = O(d\log d)$로 생각해도 무방하다.$\mathbb{F}$는 덧셈, 뺄셈, 곱셈, 나눗셈..

블로그를 최근에 잘 하지 않았네요. 최근에 쓴 글 간단히 업로드합니다.

최근 jo_on님을 통해 알게 된 내용을 정리해 보았다. Theorem (Dilworth). Finite POSET \(P\)에 대해, \(P\)의 minimum chain cover의 크기는 \(P\)의 maximum antichain의 크기와 같다. 이 글에서는 Dilworth's theorem의 constructive pf를 목표로 한다. POSET과 Mirsky's theorem에 대해서는 전에 대충 써놓은 글이 있다. 1. Non-constructive proof \(\newcommand{\abs}[1]{| #1 |}\)가장 잘 알려져 있는 증명법이기도 하다. Construction과는 그다지 관계가 없으니 관심없다면 스킵해도 될 듯. \(P\)의 크기에 대해 귀납법을 사용하자. \(P\)의 m..