구사과

많은 일반적인 알고리즘은 하나의 프로세서에서 작동함을 가정하지만, 현실의 계산에서는 컴퓨팅 기계가 하나의 프로세서가 아닌 여러 프로세서를 사용할 수도 있다. Parallel Algorithm의 경우는 효율성을 위해서 여러 개의 프로세서를 두고 동시에 중앙적으로 컨트롤하지만, 가끔은 여러 프로세서를 두는 것이 단순 효율성 때문이 아니라 실제적인 시공간적 제약에 의해서일 수도 있다. 예를 들어, 세계 각지에서 정보를 모으는 컴퓨터가 있고, 이 정보들을 한데 모아서 특정한 계산을 하고 싶은데, 정보들이 하나로 모으기에는 너무 크거나, 아니면 장거리 네트워크를 사용하는 것이 아주 비효율적인 상황들이 있을 것이다. Distributed Algorithm이란 어떠한 알고리즘이 하나의 프로세서가 아니라 여러 분할된 ..

1. Separating Hyperplane Theorem 2차원 평면에 겹치지 않는 두 원이 있을 때, 두 원을 분리하는 직선을 찾을 수 있을까? 다시 말해, 직선의 한 쪽에 첫 번째 원이, 직선의 다른 쪽에 두 번째 원이 존재하게 직선을 그을 수 있을까? 어렵지 않게, 두 원의 공통 접선을 적절히 그어서 나누면 될 것이다. 같은 원리로, 겹치지 않는 두 볼록 다각형이 있을 때 둘을 분리하는 직선 역시 찾을 수 있다. 조금 더 복잡하지만, 3차원 공간에서도 겹치지 않는 두 볼록 다면체를 분리하는 평면이 존재할 것 같다. 즉, 평면의 한 쪽에 볼록 다면체 하나가, 다른 한 쪽에 볼록 다면체 하나가 있는 것이다. 이를 $n$ 차원으로 일반화하면 다음과 같다. 두 개의 Disjoint한 ($A \cap B ..

알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 알고리즘 연구에서 분할 정복이 가지는 중요성은 어마어마하지만, 그래프에 대한 분할 정복에 대해서는 좋은 결과를 얻지 못했다. 오랜 시간 동안 이러한 분할 정복 은 트리, 평면 그래프, 혹은 이와 유사한 그래프에서만 가능한 것으로 알려져 있었다. 하지만, 그래프 알고리즘과 최적화 이론의 결합이 여러 의미 있는 성과들을 내면서, 이러한 분할 정복 기법을 그래프에서도 적용할 수 있는 좋은 프레임워크가 생겼고, 그 결과 중 하나가 Expander Decomposition이다. Expander는 잘 연결된 그래프를 뜻한다. 보통 그래프..

(첨부 자료는 발표에 사용한 슬라이드이다.) 이론전산학에서 논의되는 가장 주된 문제 중 하나는 어떠한 문제가 "쉽다" (algorithm) 내지는 "어렵다" (hardness) 는 논의이다. 쉽다는 것을 증명하려면, 효율적인 알고리즘을 찾아 빠르게 해결하면 된다 (constructive proof). 대단히 명료하고, 알고리즘 대회를 통해서 많이 연습되는 방법이기도 하다. 어렵다는 것을 증명하는 것은 쉽다를 증명하는 것만큼 명료하지 않다. $P=NP$ 가설이 오랜 난제로 남아있는 것도 "어려움을 증명하는" 쉬운 방법을 찾지 못해서라고 볼 수 있다. 통상적으로는, 가장 대표성있는 문제를 잡아서 "어떠한 문제는 풀 수 없다" 라는 가설을 만들고, 이 문제가 풀렸을 때 다른 문제를 풀 수 있는 알고리즘을 고안..

이 글에서는 Monika Henzinger, Andrea Lincoln, Stefan Neumann, Virginia Vassilevska Williams의 Conditional Hardness for Sensitivity Problems 라는 논문을 요약한다. 이론 전산에서 Dynamic algorithm은, 입력 데이터에 작은 변화가 점진적으로 가해지더라도 데이터에 대해 물어볼 수 있는 특정한 문제들의 답을 그대로 보존하는 알고리즘을 뜻한다. 예를 들어서, 그래프의 "연결성" (connectivity) 를 보존하는 dynamic algorithm은 입력 그래프에 간선 추가와 제거가 이루어질 때 $s - t$ 간에 경로가 있는지 여부의 쿼리를 반환할 수 있다. 최근 이루어진 여러 연구를 통해서 Dyna..

근사 알고리즘(Approximation algorithm)은, 문제에 대한 최적해를 제공하지는 못하나, 최적해에 근접한 해(근사해)를 빠른 시간에 찾는 알고리즘이다. NP-Complete인 문제들은 $P \neq NP$ 인 이상 최적해를 다항 시간에 구할 수 없는데, 이러한 문제를 회피하는 여러 방법 중 가장 많이 연구되는 방법 중 하나가 근사 알고리즘이다. 근사 알고리즘의 목표는, 최적해에 근접함이 보장된 해를 다항 시간에 찾는 것이며, 가능하다면 그 보장의 정도를 최대한으로 끌어오는 것이다. 모든 문제가 근사 알고리즘으로 쉽게 해결되었으면 정말 좋았겠지만 당연히 세상 일이 그렇게 되지는 않는다. 어떠한 문제들은 $P \neq NP$ 인 이상 최적해를 다항 시간에 구할 수 없을 뿐만 아니라, 근사 알고..

https://epubs.siam.org/doi/epdf/10.1137/1.9781611973099.139 Andreas Bjorklund는 그래프 이론에 대수적 방법을 접목시켜서 50년짜리 SOTA를 여럿 깬 것으로 유명하다. 최근에 논문 중 하나를 읽어볼 기회가 생겼는데 생각보다 훨씬 elementary한 방법이라서 놀랐다. 간단하게 요약하면 좋을 것 같아서 짧은 노트를 써 본다. 문제는 "그래프가 있고 K개의 정점이 마크되어 있을 때 이 정점들을 모두 지나는 최소 길이 simple cycle을 찾는 문제" 이고, 시간 복잡도 aim은 $O(2^k poly(N))$ 이다. 풀이는 다음과 같다. 먼저 찾을 사이클의 시작점을 $k$ 개 중 하나로 고정하자. 다음과 같은 walk $w = \{s, v_1,..

일반적인 그래프에서 효율적으로 해결할 수 있는 문제들을, 간선이 추가되고 제거되는 등의 업데이트가 가해질 때도 효율적으로 해결할 수 있는지를 연구하는 분야를 Dynamic Graph Algorithm이라고 부른다. 이 분야에 대해서는 최근 많은 연구가 진행되고 있으며, 여러 차례의 멤버십 글로도 이 분야의 다양한 최신 기술과 테크닉을 소개한 바 있다. 이 글에서 소개할 주제는 Decremental Graph Algorithm을 얻을 수 있는 프레임워크 중 하나인 Congestion Balancing 이다. 어떠한 알고리즘이 decremental하다는 것은, 간선 추가 쿼리는 처리할 수 없으나 제거 쿼리는 처리할 수 있다는 것을 뜻한다. Decremental algorithm 그 자체로는 실용적 가치가 존..

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..

가중치 있는 방향 그래프 $G$ 에서 두 정점 $s, t$ 가 쿼리로 주어질 때, $s$ 에서 $t$ 로 가는 최단 경로를 구하는 문제를 흔히 모든 쌍 최단 경로 문제 (All-Pair Shortest Path, APSP) 문제라고 부른다. APSP 문제는 그래프 이론의 기초적인 문제 중 하나로, Floyd-Warshall Algorithm을 사용하여 $O(n^3)$ 시간에 해결하는 방법이 아주 잘 알려져 있으며 알고리즘을 공부하다 보면 누구나 접하게 될 기초 알고리즘 중 하나이다. Floyd Warshall Algorithm은 APSP 문제에 대해서 다음과 같은 자료구조를 만드는 알고리즘이라고 볼 수 있다: 자료 구조의 초기화에는 $O(n^3)$ 이 걸린다. 자료 구조는 $O(n^2)$ 의 메모리를 사..