티스토리 뷰

가중치 있는 방향 그래프 $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)$ 의 메모리를 사용한다.
  • 자료 구조는 각 쿼리를 $O(1)$에 처리한다.

여기서 Floyd-Warshall Algorithm을 Dijkstra로 대체할 경우 초기화 시간을 $\tilde{O}(mn)$ 으로 최적화 할 수 있다. 많은 전문가들은 APSP는 이보다 더 빠르게 해결할 수 없다고 믿는다 (APSP Conjecture).

Distance-Sensitivity Oracle (DSO)는 APSP 문제를 일반화하는 문제로, 각 쿼리에서 두 정점 $s, t$ 와 실패 위치 $f$가 주어진다. 실패 위치는 하나의 간선이나 하나의 정점이다. 쿼리가 주어지면, 우리는 $s$ 에서 $t$ 로 가며 $f$를 지나지 않는 최단 경로를 찾아야 한다. 단순하게는, APSP 알고리즘을 모든 $f$ 에 대해서 수행함으로써 $O(n^3m)$ 시간에 $O(n^2m)$ 메모리를 사용하는 자료구조를 만들 수 있다. 일반 그래프에 대해서는 이 문제에 대한 많은 연구가 이루어져 있으며, 2017년 기준 $\tilde{O}(nm)$ 시간과 $O(n^2)$ 메모리로 DSO 문제를 해결할 수 있다. 이는 이 문제의 하위호환인 APSP와 동일한 시간/메모리 를 사용하며, APSP Conjecture에 의해 APSP를 이보다 더 빠르게 풀 수 없다면, DSO 역시 이보다 더 빠르게 해결할 수는 없을 것이다.

하지만, 간선의 가중치가 $[-M, M]$ 이며 그래프가 Dense하다면 ($m = \Theta(n^2)$), APSP를 더 빠르게 해결할 수 있다는 사실이 잘 알려져 있다. 예를 들어, Undirected graph에서는 APSP를 $\tilde{O}(n^{\omega} M)$ 에 풀 수 있으며, Directed graph에서는 APSP를 $O(n^{2.5286}M)$ 에 해결할 수 있다 (Zwick '02). 이러한 결과로 미루어 봤을 때, DSO에서도 비슷한 방식으로 빠른 알고리즘이 있는지를 자연스럽게 질문할 수 있다. 이에 대한 정답은 (거의) 참으로 밝혀졌으며, Chechik과 Cohen은 $O(n^{2.873}M)$ 시간에 작동하며 각 쿼리를 polylogarithmic time에 처리하는 DSO를 구성하였다.

모든 간선의 가중치가 양수라고 가정하면, Constructing a Distance Sensitivity Oracle in $O(n^{2.5794}M)$ Time 라는 논문은 $O(n^{2.5794}M)$ 시간에 $O(1)$ 쿼리를 지원하는 DSO를 구성할 수 있음을 보인다. 이는 APSP와 $O(n^{0.051})$ 배 차이밖에 나지 않는 결과로, DSO와 APSP의 Gap을 크게 줄이는 결과이다. 이 글에서는 이 논문의 내용을 요약한다.

1. Introduction

이 논문의 Main result는 다음과 같다.

Theorem 1. 간선의 가중치가 ${1, 2, \ldots, M}$ 중 하나인 방향 그래프 $G = (V, E)$ 가 주어지면, $O(n^{2.5794}M)$ 시간에 전처리하고, $O(1)$ 시간에 쿼리를 지원하는 DSO를 구성할 수 있다.

Remark on Theorem 1. 알고리즘의 Exponent에 $\omega$ 가 등장하지 않는 이유는, 이 알고리즘이 정사각형 행렬을 곱하는 것이 아니라 직사각형 행렬을 곱하기 때문이다.

이제 이어지는 내용은 Theorem 1을 증명하기 위해 사용된다.

2. Technical Preliminaries

Main Result를 증명하기 위해서는 $x^r$ Modulo 상에서 Polynomial matrix의 역행렬을 계산해야 한다. $r$ 을 어떠한 정수, $\mathbb{F}$ 를 어떠한 유한 체 (Finite field), $F \in \mathbb{F}[x]^{n \times n}$ 를 각 항이 $d$ 차 다항식인 행렬이라고 하자. 다음 내용이 성립한다.

Theorem 2 (Proof omitted in this article). $F^{-1} \mod x^r$ 를 $\tilde{O}(dn^{\omega}) + (r^2/d) \times MM (n, nd/r, nd/r) \times n^{o(1)}$ 시간에 계산할 수 있다.

이 때 $\omega$ 는 행렬 곱 알고리즘의 지수부 상수이다. 현재 $\omega \le 2.3728596$ 임이 알려져 있다. $MM(n_1, n_2, n_3)$ 은 $n_1 \times n_2$ 행렬과 $n_2 \times n_3$ 행렬을 곱하는 데 걸리는 시간이다. 이 Theorem의 증명이 이 논문에 나와 있지만, 이 글에서는 technical하여 굳이 다루지 않는다.

3. Constructing a $r$-truncated DSO in $O(n^{2.5794}M)$ time

Main Theorem을 증명하기 위해 다음과 같은 조금 더 간단한 문제를 해결한다. 이 부분이 이 논문의 핵심인데, 놀랍게도 상당히 간단한 아이디어로 해결할 수 있다.

쿼리 $(u, v, f)$ 에 대한 최단 경로를 $l$ 이라고 할 때, $l$ 을 반환할 수는 없지만, $min(l, r)$ 을 반환할 수 있는 DSO를 $r$-truncated DSO 라고 정의한다. 이제 이러한 $r$-truncated DSO 를 $\tilde{O}(dn^{\omega}) + (r^2/d) \times MM (n, nd/r, nd/r) \times n^{o(1)} = O(n^{2.5794}M)$ 시간에 계산할 수 있는 알고리즘을 제시한다.

$\mathbb{F}$ 를 충분히 큰 유한체, 예를 들어 $Z_p$ 라고 하고, 그래프 $G$ 에 대해 $A(G)$ 라는 행렬을 다음과 같이 정의하자.

  • 만약 $u \rightarrow v$ 로 가는 가중치 $l$ 의 간선이 존재한다면, $A(G){u, v} = a{u, v} x^l$ 이다. 이 때 $a_{u, v}$ 는 $\mathbb{F} \setminus {0}$ 에 속하는 어떤 랜덤 원소이다.
  • 모든 $v$ 에 대해서 $A(G)_{v, v} = 1$ 이다.

다음과 같은 사실이 잘 알려져 있다. (최근 카이스트 교내 대회에도 이에 관련된 문제가 출제되었다.)

Lemma 3.1 (Sankowski, 2005). $A(G)$ 의 adjoint matrix를 $adj(A(G))$ 라고 할 때, $adj(A(G))_{u, v}$ 의 최소차항의 차수는 $u$ 에서 $v$ 로 가는 최단 경로의 길이와 높은 확률로 일치한다.

Proof of Lemma 3.1. $P(n)$ 을 길이 $n$ 의 모든 수열의 집합이라 하면, 정의에 의해 $adj(A(G))_{u, v} = \sum_{p \in P(n), p_v = u} \prod_{k \in [n] \setminus \{v\}} A(G)_{k, p_k}$ 이다. 그래프 이론적으로 해석했을 때, 이것은 모든 정점들을 사이클과 $u \rightarrow v$ 로 가는 경로로 분해하고, 분해에 사용된 간선의 가중치 합을 곱한 것이다. 만약 최단 경로가 $u \rightarrow v$ 를 잇는 사이클로 분해되고, 최단 경로에 속하지 않는 정점들에 대해 Self-loop로 분해한다면, 최소 차항이 $dist(u, v)$ 인 항을 하나 얻을 수 있다. 고로 $adj(A(G))_{u, v}$ 의 $dist(u, v)$ 차항은 높은 확률로 0이 아니다. 역으로, $adj(A(G))_{u, v}$ 에 어떤 0이 아닌 $k$ 차항이 존재한다고 하자. 사이클에 있는 간선들을 모두 지워주면 $u \rightarrow v$ 로 가는 길이 $k$ 이하의 경로를 얻을 수 있다. 종합하면, $adj(A(G))_{u, v}$ 의 최소 차항과 $dist(u, v)$ 는 일치한다는 결론을 얻는다. $\blacksquare$

다음과 같은 사실은 훨씬 더 잘 알려져 있다.

Theorem 3.2 (Sherman-Morrison-Woodbury Formula) Field $\mathbb{F}$, Invertible matrix $A \in \mathbb{F}^{n \times n}$, Column vector $u, v \in \mathbb{F}^n$ 에 대해서, $\gamma = 1 + v^T A^{-1} u$ 라고 하자. $\gamma$ 가 Invertible하다면 $A + uv^T$ 역시 invertible하고,

  • $det(A + uv^T) = \gamma det(A)$
  • $(A + uv^T)^{-1} = A^{-1} - \gamma^{-1} (A^{-1} u v^T A^{-1})$
  • $adj(A + uv^T) = det(A + uv^T) (A + uv^T)^{-1} = det(A) (\gamma A^{-1} - A^{-1} uv^T A^{-1})$

또한 Schwartz-Zippel Lemma를 사용한다.

Theorem 3.3 (Schwartz-Zippel Lemma) Field $\mathbb{F}$ 에서 $p(x_1, x_2, \ldots, x_m)$ 을 총 차수가 $d$ 이하인 0이 아닌 다항식이라고 하자. $S$ 를 $\mathbb{F}$ 의 유한한 부분집합이라 하고, $r_1, r_2, \ldots, r_m$ 을 $S$ 에서 independently, uniformly sampled한 변수라고 할 때, $Pr[p(r_1, r_2, \ldots, r_m) = 0] \le \frac{d}{|S|}$ 이다.

$F \in \mathbb{F}[x]^{n \times n}$ 를 각 항이 $d$ 차 다항식인 행렬이라고 하자. 다음 내용이 성립한다.

Theorem 3.4. $det(F)$ 를 $\tilde{O}(dn^\omega)$ 번의 field operation으로 계산할 수 있다.

이를 Theorem 2와 결합하면

Corollary 3.5. $adj(F) \mod x^r$ 을 $\tilde{O}(dn^{\omega}) + (r^2/d) \times MM (n, nd/r, nd/r) \times n^{o(1)}$ 시간에 계산할 수 있다.

이제 알고리즘에 대한 설명을 할 준비가 완료되었다.

3.1 Preprocessing Algorithm

전처리 알고리즘은 아주 간단하다. 충분히 큰 상수 $C$ 에 대해서 단순히 $p \in [n^C, 2n^C]$ 를 구하고, $\mathbb{F} = \mathbb{Z}_p$ 로 둔다. 그리고 위에서 설명한 것과 같이 $A(G)$ 를 만들고, Theorem 2, Theorem 3.4 에 의해 $A(G)^{-1}, det(A(G))$ 를 구한다. 이것으로 전처리 알고리즘이 종료된다.

3.2 Query Algorithm

쿼리 알고리즘 역시 간단한 편이다. Theorem 3.2에 설명된 Sherman-Morrisson-Woodbury를 사용하면, 간선이나 정점을 지운 후의 Adjoint matrix를 쉽게 계산할 수 있다. 위 수식을 그대로 사용할 경우 $O(n^2)$ 시간에 새로운 Adjoint matrix를 구할 수 있고 이것만으로도 이미 Naive algorithm보다 효율적이다. Theorem 3.2의 역행렬이 누적되는 형태가 아니며, 각 쿼리에서 우리가 원하는 것은 전체 Adjoint matrix가 아니라 항 하나이기 때문에, 이 점을 활용하면 굳이 행렬을 계산할 필요 없이 항 하나를 $O(1)$ 번의 Arithmetic operation으로 구할 수 있다. 이것이 사실상 쿼리 알고리즘의 전부이지만, 완결성을 위해서 정확한 수식을 아래 첨부한다. 특별히 필요하지 않으면 웬만하면 여기서 3.3으로 넘기는 것을 추천한다.

3.2.1 Query Algorithm for Edge Failure

$e = (i \rightarrow j)$ 가 삭제되고, $x$ 에서 $y$ 로 가는 최단 경로를 계산한다고 하자. $A(G)_{i, j}$ 에 $-a_{i, j}x^{w(i, j)}$ 을 더해야 한다. 이는 $u = e_i, v = -a_{i, j}x^{w(i, j)} e_j$ 일 때 $A^\prime(G) = A(G) + uv^T$ 를 설정하는 것과 같다. Theorem 3.2를 적용시킬 준비를 하자.

  • $\gamma = 1 + v^T A(G)^{-1} u$
  • $\beta = (A(G)^{-1} uv^T A(G)^{-1})_{x, y}$

이 항들은 모두 $O(1)$ 시간에 계산 가능하다:

  • $\gamma = 1 + v^T A(G)^{-1} u = 1 - a_{i, j} x^{w(i, j)} A(G)^{-1}_{j, i}$
  • $\beta = (A(G)^{-1} uv^T A(G)^{-1})_{x, y} = -A(G)^{-1}_{x, i} z_{i, j} A(G)^{-1}_{j, y} x^{w(i, j)}$

이제 $A^\prime(G)_{x, y} = det(A(G)) (\gamma A(G)^{-1}_{x, y} - \beta)$ 이니 $O(1)$ 번의 arithmetic operation으로 쿼리의 정답을 계산할 수 있다.

3.2.2 Query Algorithm for Vertex Failure

정점 $f$ 가 삭제되고, $u$ 에서 $v$ 로 가는 최단 경로를 계산한다고 하자. 일반성을 잃지 않고 $f \neq u, f \neq v$ 를 가정할 수 있다. $f$ 에서 나가는 모든 간선을 제거하는 것으로 충분하며, 이는 Row vector 하나를 $f$ 행에 더하는 rank-1 update이니 Theorem 3.2를 적용할 수 있다. $u = e_f$, $v$ 를 $A(G)^T$ 의 $f$번째 행의 역 (negation) 에서 $v_f = 0$ 을 취한 벡터라고 하자. 다시 말해

$\begin{equation}
v_j =
\begin{cases}
-a_{f, j} x^{w(f, j)}, & \text{if $f \neq j$}.\newline
0 & \text{otherwise}.
\end{cases}
\end{equation}$

이제 $A^\prime(G) = A(G) + uv^T$ 이다. Theorem 3.2를 적용시킬 준비를 하자.

  • $\gamma = 1 + v^T A(G)^{-1} u$
  • $\beta = (A(G)^{-1} uv^T A(G)^{-1})_{x, y}$

이 항들은 모두 $O(1)$ 시간에 계산 가능하다:

  • $(e_f - v)^T$ 는 정확히 $A(G)$ 의 $f$ 번째 행이다. $(e_f - v)^T A(G)^{-1} = e_f^T$. $v^T A(G)^{-1} = e_f^T A(G)^{-1} - e_f^T$ . 고로 $\gamma = 1 + e_f^T A(G)^{-1} u - e_f^T u = A(G)^{-1}_{f, f}$
  • $\beta = (A(G)^{-1} uv^T A(G)^{-1})_{x, y} = (e_u^T A(G)^{-1}u) (v^T A(G)^{-1} e_v) = A(G)^{-1}_{u, f} A(G)^{-1}_{f, v}$

이제 $A^\prime(G)_{x, y} = det(A(G)) (\gamma A(G)^{-1}_{x, y} - \beta)$ 이니 $O(1)$ 번의 arithmetic operation으로 쿼리의 정답을 계산할 수 있다.

이를 종합하여 우리는 다음과 같은 결론을 얻는다.

Theorem 3.6. 간선의 가중치가 ${1, 2, \ldots, M}$ 중 하나인 방향 그래프 $G = (V, E)$ 가 주어지면, $O(n^{2.5794}M)$ 시간에 전처리하고, $O(1)$ 시간에 쿼리를 지원하는 $r$-truncated DSO를 구성할 수 있다.

Proof of Theorem 3.6. 알고리즘의 정당성은 자명하다. 확률 분석을 해 보면, 쿼리 알고리즘이 실패할 가능성이 Theorem 3.3에 의해 $\frac{d}{|S|}$ 이하이다. Determinant는 $n$ 차 다항식이니, 대략 $O(n/n^{C}) = O(1/n^{C - 1})$ 의 확률로 실패한다는 것이다. 가능한 쿼리의 가짓수가 $O(n^4)$ 가지이니, 알고리즘은 $O(1/n^{C - 5})$ 의 확률로 틀린다. 이는 알고리즘이 높은 확률로 (w.h.p) 정답을 반환함을 뜻한다. $\blacksquare$

3.3 Constructing the Full DSO

Theorem 3.6을 통해서 $r$-truncated DSO를 만들었다. 이제 이 $r$-truncated DSO를 Black box로 사용하여 Full DSO를 구성한다.

첫 번째 알고리즘은, 쿼리 타임이 클 수 있는 $r$-truncated DSO를 받아, $O(1)$ 쿼리를 지원하게끔 하는 것이다. 이를 구체적으로 설명하면 다음과 같다.

Lemma 3.7 (Proof omitted in this article) 정수 $r$, 모든 간선의 가중치가 ${1, 2, \ldots, M}$ 인 그래프 $G = (V, E)$, 전처리 시간 $P$ 이며 쿼리 시간 $Q$ 인 임의의 $r$-truncated DSO $D$ 에 대해서, $O(1)$ 쿼리 시간과 $O(n^{2.5286}M + P + \tilde{O}(n^2)Q)$ 전처리 시간을 가지는 $r$-truncated DSO $Fast(D)$ 를 만들 수 있다.

Short explanation. $G$ 의 모든 쌍 최단 경로 행렬과, consistent 한 shortest path tree를 빠르게 구성한 후, $\tilde{O}(n^2)$ 번의 쿼리만으로 모든 중요한 정보를 표현할 수 있다는 것이 이 Lemma의 대략적인 증명이다. Lemma 자체는 Ren20의 Observation 4에서도 사용하였지만, 당시에는 $\tilde{O}(Mn^2)$ 였던 쿼리 횟수를 줄였다는 것이 이 논문의 기여 중 하나이다. 그 내용이 생각보다 길고 복잡해서, 지면 상 문제로 증명은 생략한다.

두 번째 알고리즘은, $O(1)$ 쿼리를 지원하는 $r$-truncated DSO를 받아, 쿼리 타임이 조금 큰 $(3/2)r$-truncated DSO를 만드는 것이다. 이를 구체적으로 설명하면 다음과 같다.

Lemma 3.8. 전처리 시간 $P$ 이며 쿼리 시간 $O(1)$ 인 임의의 $r$-truncated DSO $D$ 에 대해서, $\tilde{O}(nM/r)$ 쿼리 시간과 $P + O(n^2)$ 전처리 시간을 가지는 $r$-truncated DSO $Extend(D)$ 를 만들 수 있다. 이 DSO는 높은 확률로 올바르다.

Proof of Lemma 3.8. $apath(u, v, x)$ 를 $u \rightarrow v$ 로 가는 경로 중 $x$ 를 거치지 않는 최단 경로라고 하자. 모든 $u, v, x$ 에 대해, $P$ 를 $r \le |apath(u, v, x)| < (3/2)r$ 를 만족하는 $apath(u, v, x)$ 들의 집합이라고 하자. $P$ 는 $D$ 에서는 계산할 수 없지만 $Extend(D)$ 에서 계산해야 하는 집합과 정확히 일치한다.

$P$ 의 원소 $p = apath(u, v, x) \in P$ 에 대해, $mid(p)$를 $|p[u, y]| < r, |p[y, v]| < r$ 을 만족하는 정점 $y \in p$ 의 집합이라고 하자. 여기서, $p[a, b]$ 는 경로 $p$ 에서 정점 $a \rightarrow b$ 로 가는 부분경로 (subpath) 이다. 자세한 것은 아래 사진을 참조하라.

$p[u, y] = apath(u, y, x), p[y, v] = apath(y, v, x)$ 이기 때문에, $D$ 에서는 는 $apath(u, y, x), apath(y, v, x)$ 를 올바르게 찾을 수 있다. 즉, 우리가 $y$ 를 찾으면, $apath(u, v, x)$ 역시 찾을 수 있다. 또한, $|mid(p)| \geq r/3M$ 이다.

$Extend(D)$ 의 전처리 알고리즘을 설명한다. 충분히 큰 상수 $C$ 를 고정하자. 모든 정점 $v \in V$ 를 독립적으로 $min(1, 3CM \ln n/r)$ 의 확률로 샘플링하고, 샘플링된 정점들의 집합을 $H$ 로 하자. 충분히 높은 확률로 $|H| = \tilde{O}(nM/r)$ 이다.

$u, v, x \in V$ 를 고정시켰을 때, $H \cap mid(p) \neq \emptyset$ 일 확률은 $1 - (1 - 3CM \ln n / r)^{r / 3M} \geq 1 - 1/n^C$ 이다. 이를 모든 $P$ 에 속하는 $O(n^4)$ 개의 후보에 대해서 합하면, 높은 확률로 $H \cap mid(p) = \neq \emptyset$ 이 모든 $p \in P$ 에 대해서 성립한다.

이제 $Extend(D)$ 의 쿼리 알고리즘은 다음과 같다. 쿼리 $(u, v, x)$ 가 주어지면, $D(u, v, x) < r$ 일 경우 $D(u, v, x)$ 를 반환한다. 아닐 경우:

$min((3/2)r, min_{h \in H}(D(u, h, x) + D(h, v, x)))$

를 반환한다. $\blacksquare$

이 두 Lemma를 사용하면 Full DSO를 구성할 수 있다. 초기 주어진 $r$-truncated DSO를 $D^{start}$ 라고 하자. Lemma 3.7에 의해 쿼리 시간 $O(1)$ 인 $r$-truncated DSO $D_0 = Fast(D^{start})$ 을 만들 수 있다. $D_0$ 을 사용하여, 쿼리 시간 $O(1)$ 인 $(3/2)r$-truncated DSO $D_1 = Fast(Extend(D_0))$ 를 만들 수 있다. 이를 반복하면, $(3/2)^i r$-truncated DSO $D_i = Fast(Extend(D_{i-1}))$ 과 같이 계속 DSO의 범위를 넓힐 수 있으며, $i \geq \log_{3/2}(nM/r) $ 일 경우 Full DSO를 만들 수 있다. 다시 말해, $D^{final}$이 원하는 DSO라고 하면,

$D^{final} = Fast(Extend(Fast(Extend(\cdots Fast(D^{start})))))$

이다.

3.3.1 Proof of Theorem 1

$O(1)$ 쿼리를 지원하는 Full DSO를 구성했으니, 이것이 $O(n^{2.5794}M)$ 시간에 전처리됨만을 보이면 Theorem 1의 증명이 완성된다.

$\omega(a, b, c)$ 를, $n^a \times n^b$ 행렬과 $n^b \times n^c$ 행렬을 곱할 때 드는 시간 복잡도 $O(n^e)$ 의 exponent $e$ 라고 정의하자. 예를 들어 $\omega(1, 1, 1) \le 2.372.. = \omega $ 이다. 편의상 $\omega(1,1, \lambda) = \omega(\lambda)$라고 하자. 다음과 같은 Lemma들이 성립한다. (증명은 하지 않는다.)

  • 양의 실수 $a, b, c, r$ 에 대해 $r + \omega(a, b, c) \le \omega(a, b+r, c+r)$.
  • $f(\tau) = \omega(1, 1 - \tau, 1 - \tau)$ 라고 할 때 ($\tau \in [0, 1]$) $\tau + f(\tau)$ 는 단조 비증가하고, $2\tau + f(\tau)$ 는 단조 비감소한다.

$\alpha \in [0, 1]$에 대해, $r = Mn^{\alpha}$ 라고 두자. $\alpha$ 의 값은 이후 정한다. $\mu = 0.5286...$ 이라 두자. (Shortest path tree 구성에 필요했던 상수이다.)

Lemma 3.6, 3.7에서 설명한 중간 과정을 모두 포함해서 $D^{final}$ 의 전처리 시간을 표현하면:

$\tilde{O}(n^{2 + \alpha} M + n^{\omega} M + n^{2 + \mu} M) + n^{2\alpha + \omega(1, 1 - \alpha, 1 - \alpha) + o(1)} M + \sum_{i = 0}^{\lceil \log_{3/2}(nM/r) \rceil} \tilde{O}(\frac{n^{3 - \alpha} M}{(3/2)^i})$

$\le n^{max(2 + \alpha, 2 + \mu, 3 - \alpha, 2 \alpha + \omega(1, 1 - \alpha, 1 - \alpha)) + o(1)} M$

$\alpha = 0.420645, \beta = \frac{1}{1 - \alpha}$ 라고 하자. $1.5 < \beta < 1.75$ 이다. 이 때

$\omega(1, 1 - \alpha, 1 - \alpha) = (1 - \alpha) \omega(\beta) \ \le (1 - \alpha) \frac{(1.75 - \beta)\omega(1.5) + (\beta - 1.5)\omega(1.75)}{1.75 - 1.5} \ \le 0.579355 * 4 * (0.923943 \omega(1.5) + 0.226058 \omega(1.75)) $

2018년 기준 $\omega(1.5) \le 2.796537, \omega(1.75) \le 3.021591$ 이다. 고로

$2\alpha + \omega(1, 1 - \alpha, 1 - \alpha) \le 2.579384$ $\blacksquare$

'공부' 카테고리의 다른 글

2021 ICPC Seoul Regional  (0) 2021.11.23
2021 ICPC 서울 인터넷 예선  (6) 2021.10.13
APIO 2021  (1) 2021.07.29
Klein's Algorithm for Computing Edit Distance on Tree  (0) 2021.07.27
CCO 2019 Shopping Plans  (0) 2021.07.27
댓글
댓글쓰기 폼