Main Menu
Recent Posts
-
Correlation Clustering
Correlation clustering은 그래프의 정점들을 cluster들로 분할하는데, 각 간선 에는 두 종류의 weight 와 가 있다. 두 endpoint가 같은 cluster에 있으면 점, 다른 cluster에 있으면 점을 얻는다. 목표는 점수의 합을 최대화하는 clustering을 찾는 것이다. 이 문제는 NP-hard임이 알려져 있고, Max cut처럼 SDP를 이용한 constant factor approximation이 알려져 있다.이번에도 직관적인 -approximation이 있는데, 모든 정점을 한 cluster에 놓거나 / 정점을 다 다른 cluster에 두거나 둘 중 나은 것이 최적해의 절..
2025.02.10 09:33 -
Samuelson-Berkowitz Algorithm
https://www.acmicpc.net/problem/25510https://infossm.github.io/blog/2022/08/18/CharPoly/Division-Free Determinant에 대해 위 문제를 내고 글도 썼는데, 최근 훨씬 간단한 알고리즘이 있다고 해서 정리해보려고 한다.원본 글에 달린 것과 동일하게 에 동작하는 division-free characteristic polynomial 알고리즘이다.Algorithm 행렬 에 대해, 를 번째 행, 열만 따와서 만든 크기 의 정사각행렬이라고 하자. 당연히 이다.$p_{1}(x) = \det(x..
2025.02.06 11:19 -
LGV lemma [WIP]
Lindström–Gessel–Viennot lemma는 DAG의 non-intersecting path를 셀 때 사용할 수 있는 공식이다.에서 개의 정점 , 을 생각하자. 어떤 두 path가 intersecting하다는 것은 둘 사이에 공통된 정점이 있다는 것이다. path tuple 에 대해 가 를 로 보내고, 가 순열이면 이러한 를 path system이라고 하자. 가 non-intersecting이면 non-intersecting path system이라고 부르고, ..
2025.02.04 07:31 -
BOJ 21268 Do Use FFT
https://www.acmicpc.net/problem/21268솔루션에서 Tellegen's Principle을 인용하고 있어서 지난 포스트와 연관해 작성해본다. 머리 좋은 사람들은 아마 생각하지 않고도 풀 수 있을 것 같다.Without Tellegen's principle를 답이라고 하자.와 관련한 항들을 사부작거리다보면, 를 미리 계산해두면 편할 것 같다.라고 두면, $E_{k} = \sum_{j} P..
2025.01.31 00:24 -
Approximation of MAX CUT
오늘 다룰 Max Cut 문제는 non-negative weighted undirected graph 에 대해서 를 골라서 의 weight 합을 최대화하는 문제이다. 다항 시간 알고리즘이 알려진 min cut에 비해 이 문제는 NP-hard임이 알려져 있다.NP-hard problem의 경우 여러 근사 알고리즘들이 존재하는데, 가장 naive한 알고리즘부터 생각해보자. 임의의 에 대해 의 weight 합, 즉 를 라고 표기하자. 의 가능한 최댓값, 즉 MAX CUT을 $\mat..
2025.01.28 22:48 -
Bostan-Mori, Tellegen's Principle, Power series composition
Bostan-Mori algorithm흔히 "선형 점화식의 번째 항"을 구하는 알고리즘으로 알려진 방법이다. 사실은 보다 일반적으로, 꼴의 rational power series의 차항 계수를 구하는 데 사용할 수 있다.Theorem. N[x^N]f(x)\mathcal{M}(d)\mathbb{F}[x]d\mathcal{M}(d) = O(d\log d)\mathbb{F}$는 덧셈, 뺄셈, 곱셈, 나눗셈..
2025.01.23 00:47 -
BOI 2016 Swap
BOI 2016 Swap순열 이 주어질 때, 에 대해 (순서대로) 와 를 스왑할 수 있는 기회가 한 번씩 주어진다. 이를 적절히 사용하여 만들 수 있는 사전 순 최소 순열을 구하여라.풀이의 후보는 셋 뿐이고, 사전 순 최소를 생각하면 이 중 최소인 값이 번 자리에 들어가는 것이 당연하다.(자명한 경우) 번 자리에 또는 가 들어가는 경우, 번 자리가 각각 로 강제된다.(비자명한 경우) 하지만 이 들어가는 경우..
2025.01.22 08:55 -
2-approximation of minimum knapsack problem
블로그를 최근에 잘 하지 않았네요. 최근에 쓴 글 간단히 업로드합니다.
2023.12.17 16:17