Randomized algorithms - 2023.12.08

Example 1 (https://koosaga.com/319 마지막 단락)

그래프가 주어질 때 이 그래프의 maximal independent set 을 구하는 문제를 생각해 보자.

maximal independent set은 maximum independent set을 approximate할 수 없다. 하지만 maximal matching과 $\Delta+1$ edge coloring을 구하는 데 사용할 수 있고 이들은 각각 그들의 optimal variant의 constant approximation이다.

다음 과정을 정점이 1개 이상일 때까지 반복하면 된다:

• 각 노드에 $[0, 1]$ 사이의 random real을 배정한다. 이를 $r(v)$ 라고 하자.
• 만약 어떠한 노드에 대해 $\max_{w \in adj(v)} r(w) < r(v)$ 일 경우 $v$를 MIS에 넣는다.
• MIS에 넣은 정점과 그에 인접한 정점을 지운다.

위 과정을 반복하여 구한 것이 MIS임은 쉽게 알 수 있다.

위 과정은 일반적으로 $O(\log n)$ 번만 반복하면 된다. 왜냐면 매 라운드에서 남는 간선의 기댓값이 m/2이기 때문이다. 대충 n개의 원소 중 1번 원소가 최댓값일 확률이 1/n 이라는 것으로부터 시작하는데, 실제로는 과정이 조금 많다. 링크된 블로그 글을 참고하면 좋을듯. 기댓값 m/2가 WHP m/2가 아니지만, Markov Inequality에 의해 상관없다.

Example 2 (BOJ 16269)

방향 그래프의 각 노드에 대해서 해당 노드에서 도달 가능한 원소들의 개수를 $1+\epsilon$ approximate하는 문제를 생각해 보자. $O(nm)/poly(n, m)$ 이 어려움이 잘 알려진 문제이다.

편의상 그래프가 DAG라고 가정하자 (일반 케이스는 SCC를 묶고 똑같이 하면 된다.)

각 노드에 $[0, 1]$ 사이의 random real을 배정한다. 이를 $r(v)$ 라고 하자. 모든 노드에 대해서, 해당 노드에서 도달 가능한 원소 개수는 알기 어렵지만, 해당 노드에서 도달할 수 있는 $r(v)$ 최솟값은 알 수 있다. 이건 DP로 구하면 된다.

만약 해당 노드에서 도달 가능한 정점이 $k$개라고 하면, $r(v)$ 의 기댓값은 $\int_{0}^{1} (1-x)^k dx = \frac{1}{k+1}$ 이다. 그래서, 최솟값을 통해서 $k$를 역산한다는 생각을 할 수 있다.

이제 이걸 $1+\epsilon$ approximate로 구체적으로 하려면 다음과 같은 식으로 생각하면 된다. $U_k$ 를, $k$개의 independent, uniform real을 [0, 1] 에서 뽑았을 때, 최솟값의 확률 분포라고 하자. 우리는 $U_k$ 에서 $Q$ 개의 원소를 뽑았는데, $k$가 뭔지는 모른다. 원소만 보고 $k$를 맞출 수 있을까? 그러기 위해 필요한 최소 개수의 $Q$ 는 몇 개일까? $Q = \Omega(\frac{\log n}{\epsilon^2})$ 일 경우, whp로 $k$를 $1 + \epsilon$ approx할 수 있다. 아마 뽑은 값에서 역산한 k들을 가지고 1/avg(1/k) 하면 된다고 아는데, 정확한 내용은 나도 모른다.

위 결과를 사용하면 $\frac{(n+m)\log n}{\epsilon^2}$ 에 whp로 reachability count가 가능하다. Limited sample에서 확률 분포를 때려맞추는 종류의 알고리즘이 pure graph theory에도 응용될 수 있다는 점이 재밌는듯. 일종의 Sketching algorithm이라고 볼 수도 있다. Min-hashing (https://www.acmicpc.net/problem/20028?) 과도 비교해 보면 좋다.

Example 3 (https://arxiv.org/pdf/2301.10191.pdf)

$n$ 개의 정수가 주어질 때 서로 다른 정수의 개수를 $1+\epsilon$ approximate로 찾을 것이다. 근데 메모리를 $O(\log n)$ 정도만 써야 함.

Example 2번의 알고리즘을 이미 적용할 수 있다. (BOJ 20603) 적당한 해시 함수 $F(x)$ 를 잡아서 $x$ 를 적당한 random real로 보낸 다음에 (2) 의 방법을 그대로 사용하면 된다. 해시 함수가 최소 $\Omega(\frac{\log n}{\epsilon^2})$ 개 필요하니 메모리 $\Omega(\frac{\log n}{\epsilon^2})$ 에 해결된다. 모든 $x$ 에 대해 저런 좋은 성질을 만족하는 해시 함수를 Universal hash function 이라고 한다.

근데 그런 해시 함수가 뭔지 모르니까, 같은 메모리를 쓰는 다른 알고리즘을 생각해 보자.

이런 코드를 짜면 된다:

set<int> S;
double p = 1;
int thres = 100 * eps * eps / log(MAXN);
while (cin >> X) {
    if (S.count(X)) S.erase(X);
    if (rnd.next(0, 1) < p) S.insert(X);
    if (S.size() == thres) {
        Erase each element of S with probability 1/2;
        p /= 2;
    }
}
cout << S.size() / p << "\n";

Line 5에 의해서 각 상태에서 last occurence가 아닌 원소는 절대 결과에 영향을 줄 수 없게 되어 있다. last occurence들은, 살아남을 확률이 p이니, |S| / p는 good estimate가 된다. 알고리즘의 증명은 위 논문을 읽어보면 된다.