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에 두거나 둘 중 나은 것이 최적해의 절..

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

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

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

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

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