구사과

Pisinger Algorithm Subset Sum 문제는, positive integer multiset S와 정수 t가 주어졌을 때, 합이 t인 S의 부분집합이 있는지를 찾는 문제이다. S의 원소 범위가 1 이상 M 이하의 정수라고 가정하자. $M$ 에 대한 dependency가 없이 풀려면 당연히 NP-hard이다. 그냥 DP를 하면 $O(n^2M)$ 이다. 각 숫자를 prefix sum으로 처리하면 $O(nM^2)$이다. Generating function으로 $O(nM \log nM)$ 에 푸는 풀이가 비교적 최근에 발견되었다. 꽤 깔끔한 $O(nM)$ 풀이를 서술 일단 첫 번째 Lemma는, 이 문제를 모든 수가 [-M, M] 인 multiset S에서 합이 1 = F[j][k + a[i]]..

그래프의 최대 유량 (Maximum Flow) 를 찾는 문제는 웬만한 알고리즘 대회 입문서에는 다 소개되어 있는 중요한 문제이다. 일반적으로 최대 유량을 찾기 위해서는 Edmonds-Karp, Dinic과 같은 알고리즘을 사용한다. 이 알고리즘의 특징은 빈 그래프에서 시작해서 유량을 증가시키는 "증가 경로" 를 찾는 것을 반복하는 식으로 작동한다는 것이다. Dinic 알고리즘은 최악의 경우 $O(V^2E)$ 에 작동하지만 실제로는 이보다 훨씬 효율적으로 작동한다. 하지만 그럼에도 선형 시간에 가까울 정도로 빠르지는 않고, 한계가 분명히 있는 알고리즘이다. 이 글에서는 Push-relabel 이라고 하는 새로운 플로우 알고리즘을 설명한다. 예전에 유량 관련 알고리즘을 정리할 때도 간략하게 설명한 적이 있는..

1. Introduction MapReduce 라는 프로그래밍 프레임워크는 대용량의 데이터를 처리하는 데 있어서 높은 성능을 보여주고, Apache Hadoop과 같은 오픈 소스 구현체들을 통해서 실용적으로도 그 가치를 증명하였다. 이 글에서는 그래프 최적화 문제를 푸는 데 효과적인 방법 중 하나인 Primal-Dual Method를 MapReduce 프레임워크에서 적용하는 새로운 프레임워크를 소개하고, 이를 통해서 Densest Subgraph Problem의 Near-linear time algorithm을 얻고자 한다. 정확히는, 이 글에서는 $O(\frac{\log n}{\epsilon^2})$ 번의 MapReduce iteration을 통하여 Densest Subgraph problem의 $(1..