최대 흐름 문제(maximum flow problem)은 유명한 조합론적 최적화 문제 중 하나입니다. 이 문제는 시점과 종점이 있는 어떤 흐름 네트워크(flow network)가 주어졌을 때, 최대한 많은 양의 유체를 시점에서 종점으로 흘리는 방법을 찾는 문제입니다. 자세한 내용은 이전 포스트에서 정리하였으니 궁금하신 분은 참조하시기 바랍니다.
2020/08/29 - [조합론적 최적화/Flow & Circulation] - 최대 흐름 문제 이해하기 (Maximum Flow Problem)
최대 흐름 문제 이해하기 (Maximum Flow Problem)
여러분이 상수도 공사의 직원이라고 해봅시다. 여러분의 업무는 물이 저장된 수원에서 물이 필요한 특정 지역까지 물을 공급하는 것입니다. 물을 공급하는 방법은 수원에서 해당 지역까지 연결
gazelle-and-cs.tistory.com
이번 시간에는 이 문제를 다음과 같이 어렵게 만들어 보겠습니다. 이해를 돕기 위해서 다음과 같은 예시를 먼저 생각해 보죠. 여러분이 어느 지역의 인터넷을 독점적으로 공급하는 인터넷 서비스 제공자(Internet service provider, ISP)라고 합시다. 인터넷이란 무엇인가요? 이는 결국 컴퓨터, 스마트폰, 서버 등 여러 단말을 연결하는 총체적인 망을 뜻합니다. 이때, 모든 단말 사이를 연결하기에는 재정적으로 부담이 되므로, 대신 라우터(router)를 두고 이들 사이를 연결하여 줍니다. 인터넷 상에서 두 단말은 여러 대의 라우터를 거쳐서 통신하게 되죠. 그리고, 이 지역에서 여러분이 갖고 있는 것이 바로 여러 대의 라우터와 라우터들을 연결하는 회선으로 이루어진 망(network)입니다.
이제 여러분의 망을 여러 사용자가 사용한다고 하고 각 사용자는 한 단말에서 다른 단말까지 지속적으로 연결된 상태를 원한다고 합시다. 이때 여러분은 사용자에게 최적의 서비스를 제공하기 위해서 망 위에서 정확히 하나의 경로로만 두 단말을 연결해 주고자 합니다. 만약 두 단말이 여러 경로를 통해 정보를 주고 받으면 먼저 들어와야 하는 정보가 늦게 들어올 수도 있고, 반대로 늦게 들어와야 하는 정보가 일찍 들어올 수도 있기 때문입니다. 그러면 전체적으로 서비스의 품질이 저하되겠죠.
여기서 문제는 라우터들을 연결하는 회선의 용량입니다. 만약 많은 사용자의 연결 경로가 어느 한 회선에 집중된다면 해당 회선의 처리 속도가 늦어지게 되고, 자연스럽게 사용자의 불편을 초래하게 될 겁니다. 따라서 여러분의 목표는 모든 사용자마다 각자가 원하는 단말 쌍을 하나의 경로로 연결하여 주되, 한 회선을 지나가는 경로의 개수를 최소화하는 것이 되겠습니다.
앞에서 소개한 문제가 바로 다품종 정수 흐름 문제(multicommodity integral flows problem)입니다. 여기서 품종이 다양하다는 것은 우리가 관리하는 흐름마다 일종의 꼬리표가 달려 있어서 이들이 서로 섞일 수 없다는 것을 의미합니다. 최대 흐름 문제에서는 물이나 가스 등과 같은 유체를 어떤 흐름 네트워크 상에서 흘리는 것이므로 어떤 지점에서 합쳐질 수 있었겠지만, 다품종 흐름 문제에서는 각 사용자는 배정 받은 경로를 통해 정보를 주고받으므로 이들이 서로 섞이면 안됩니다. 따라서 우리는 이를 따로 관리해주어야 하죠.
안타깝게도 이 문제는 사용자가 두 명인 경우에도 NP-난해(NP-hard)하다는 점이 알려져 있습니다 ([1]). 따라서 우리는 이를 근사적으로 해결하는 방법을 모색해야 합니다. 이번 시간에는 선형 계획법(linear programming)과 확률의 특성을 활용하면 좋은 근사해를 기대할 수 있다는 것을 알아보고자 합니다. 좀더 자세히 말해 아래에서는 라우터와 단말의 총 개수가 \(n\)일 때 높은 확률로 \( O(\frac{\log n}{\log \log n}) \)의 근사비를 기대하는 근사 알고리즘을 소개합니다.
문제 정의
앞에서 본 문제를 엄밀히 정의하도록 하겠습니다. 문제의 입력으로는 어떤 방향이 있는 그래프 \(G = (V, E)\)와 함께 \(k\) 개의 정점 쌍 \((s_1, t_1), \cdots, (s_k, t_k) \in V \times V\)가 주어집니다. 위 예시의 라우터와 단말이 \(V\)에, 각 사용자 \(i\)가 지속적으로 연결되기를 원하는 두 단말이 \( (s_i, t_i) \)에 대응한다고 생각하면 됩니다. 흐름 네트워크에서도 그러하였듯이 \(G\)에는 루프(loop)나 평행 간선(parallel edge)가 존재하지 않는다고 가정합니다.
우리는 모든 \(i = 1, \cdots, k\)에 대해 \(G\) 위에서 \(s_i\)와 \(t_i\)를 연결하는 경로 \(P_i\)를 만들어야 합니다. 그러면 어떤 간선은 여러 경로가 지날 수 있는데, 우리의 목표는 어떤 간선을 지나는 경로의 최대 개수를 최소화하도록 \(P_i\)를 찾는 것입니다. 다시 말해,
\[ \min_{P_1, \cdots, P_k} \max_{e \in E} \sum_{i = 1}^k |e \cap P_i| \]
를 구하는 것입니다.
선형 계획법으로 표현하기
이 문제의 이름이 다품종 정수 흐름 문제인 이유는 \(P_i\)가 \(s_i\)에서 \(t_i\)로 가는 흐름(flow)으로 볼 수 있기 때문입니다. 사실, 최대 흐름 문제에서의 흐름은 시점과 종점을 제외한 모든 지점에서 흘러 들어오는 양과 나가는 양이 동일하다는 흐름 보존 제약(flow conservation constraint)과 함께 어떤 간선에서도 흐르는 양이 용량을 초과하지 않는다는 용량 제약(capacity constraint)를 만족하는 함수로 지칭하였습니다. 하지만, 이 문제에서는 간선마다 용량이 정의되지 않고, 대신 각 사용자마다 하나의 경로를 제공해 주어야 하죠. 경로에서는 양 끝점을 제외하고는 모든 정점마다 들어오고 나가는 간선의 개수가 동일하므로, 이는 각 사용자마다 1의 흐름양(value of flow)을 제공해야 한다는 조건으로 볼 수 있습니다. 목표도 이와 함께 달라지는데, 원래는 최대로 흐를 수 있는 방법을 찾는 것이었다면, 이 문제에서는 어느 간선이든지 최소로 사용하는 방법을 찾는 것이 되었죠.
따라서, 우리는 이 문제를 다음과 같은 정수 계획법(integer programming)으로 표현할 수 있습니다. 여기서, \( f^i_e \)를 사용자 \(i = 1, \cdots ,k\)의 경로가 간선 \(e \in E\)를 지난다는 것을 나타내며, \(W\)는 어느 간선에 흐르는 경로 개수의 최댓값을 나타냅니다. 또, 어떤 정점 \(v \in V\)에 대해, \(v\)에서 나가는 간선들은 \( \delta^+(v) \), 들어오는 간선들은 \( \delta^-(v) \)로 표현하였습니다.
\[ \begin{array}{rrll} \text{minimize} & W & & \\ \text{subject to} & \displaystyle \sum_{i = 1}^k \sum_{e \in E} f^i_e & \leq W, & \\ & \displaystyle \sum_{e \in \delta^+(v)} f^i_e - \sum_{e \in \delta^-(v)} f^i_e & = 0, & \forall i = 1, \cdots, k, \forall v \in V \setminus \{s_i, t_i \}, \\ & \displaystyle \sum_{e \in \delta^+(s_i)} f^i_e - \sum_{e \in \delta^-(s_i)} f^i_e & = 1 & \forall i = 1, \cdots, k, \\ & f^i_e & \in \{0, 1\} & \forall i = 1, \cdots, k, \forall e \in E. \end{array} \tag{1} \]
첫 번째 제약 조건은 어느 간선에 흐르는 경로의 최댓값을 결정합니다. 두 번째는 각 사용자마다 흐름 보존 제약을 만족한다는 것을 나타내며 세 번째 조건은 그것의 흐름양이 정확히 1이라는 것을 보여줍니다. 마지막 정수 조건과 함께 위 제약 조건들은 각 사용자 \(i\)마다 정확히 \(s_i\)에서 \(t_i\)로 향하는 하나의 경로를 유지한다는 것을 알 수 있습니다.
하지만 정수 계획법은 풀기 어렵다고 잘 알려져 있습니다. 따라서 우리는 마지막 정수 조건을
\[ f^i_e \geq 0, \quad \forall i = 1, \cdots, k, \forall e \in E \]
과 같이 완화(relax)된 조건으로 대체하여 주는 경우가 많습니다. 이렇게 얻은 것을 우리는 종종 선형 계획 완화(linear programming relaxation)라고 부릅니다. 이렇게 얻은 선형 계획법 문제는 다항 시간에 해결할 수 있다는 것이 잘 알려져 있습니다. (그 이유를 좀 더 설명 드리자면, 변수의 개수와 제약 조건의 개수가 모두 원래 입력의 다항식으로 표현될 수 있기 때문에 그렇습니다.)
그러나 완화된 문제를 풀어서 얻는 답은 원래 문제에서 가능한 답(feasible solution)이 아닐 수 있습니다. 당장, 다음 그림을 살펴보면, 정수 조건이 있는 경우의 최적해는 2가 되지만, 완화된 문제에서의 최적해는 1.5가 된다는 사실을 알 수 있습니다.
그럼에도 완화된 문제가 도움이 되는 이유는 원래 문제의 최적해의 하한(lower bound)을 형성해 주기 때문입니다. 다시 말해, (정수 계획법 문제를 풀어 얻은) 원래 최적값을 \( W^\star_\mathsf{IP} \), 완화된 선형 계획법 문제를 풀어 얻은 최적값을 \( W^\star_\mathsf{LP} \)라고 했을 때, 항상 \[ W^\star_\mathsf{IP} \geq W^\star_\mathsf{LP} \tag{2} \]를 만족합니다. 그 이유는 원래의 정수 계획법 문제에서 가능한 답은 완화된 문제에서도 여전히 가능하기 때문입니다.
경로의 확률 분포 추출하기
이제부터 \(f\)를 완화된 문제에서의 최적해라고 하겠습니다. 정수 조건이 없어도 \(f^i\)는 흐름 보존 제약을 만족하기 때문에 일종의 흐름입니다. 그리고 놀랍게도, \(f^i\)가 1의 흐름양을 갖기 때문에 우리는 각 사용자 \(i\)마다 \(f^i\)를 주변 분포(marginal distribution)로 하는 경로의 확률 분포를 얻을 수 있습니다.
좀 더 엄밀히 설명해 보겠습니다. 각 사용자 \(i\)에 대해 \( s_i \)에서 \(t_i\)로 가는 모든 경로의 집합을 \( \mathcal{P}_i \)라고 하겠습니다. 그러면 우리는 다음의 정리를 증명할 수 있습니다.
정리 1. 흐름과 경로의 확률 분포
완화된 선형 계획법 문제의 최적해를 \(f\)라고 하자. 그러면 각 사용자 \(i\)마다 주변 분포가 \( f^i \)인 \( \mathcal{P}_i \)위의 확률 분포 \( \mathcal{D}_i \)가 존재한다. 다시 말해, 임의의 간선 \(e \in E\)에 대해 \(\mathcal{D}_i\)는 \[ Pr_{P \sim D_i}[ e \in P ] = f^i_e \]를 만족한다. 또한, \( \mathcal{D}_i \)에서 0보다 큰 확률을 갖는 경로의 개수(즉, 서포트(support)의 크기)는 간선의 개수를 넘지 않는다.
[증명] 먼저 일반성을 잃지 않고 우리는 \(f^i_e\)의 값이 0보다 큰 간선으로만 이루어진 서브그래프에 순환(cycle)이 존재하지 않는다고 가정할 수 있습니다. 만약 순환이 존재한다면 순환을 이루는 간선 위의 가장 작은 \(f^i_e\)를 다른 모든 간선에서 빼 주어도 \(f^i\)가 흐름이라는 조건을 위배하지 않습니다. 게다가 해당 간선에 흐르는 흐름의 총량은 감소하기만 할 뿐이므로 최적성(optimality)에 영향을 주지 않게 됩니다.
이제부터 다음을 만족하는 \( g \in \mathbb{R}^E \)와 가중치 \( w : \mathcal{P}_i \rightarrow \mathbb{R}_+ \)를 유지해 보도록 하겠습니다.
- 임의의 간선 \(e \in E\)에 대해, \( 0 \leq g_e \leq f^i_e \)를 만족한다.
- \(s_i\)와 \(t_i\)를 제외한 임의의 정점 \(v \in V \setminus \{s_i, t_i\} \)에 대해 \( \sum_{e \in \delta^+(v)} g_e = \sum_{e \in \delta^-(v)} g_e \)이다.
- 임의의 간선 \(e \in E\)에 대해, \( g_e + \sum_{P \in \mathcal{P}_i : e \in P} w(P) = f^i_e \)이다.
즉, 조건 1과 2는 \(g\)가 흐름이라는 것을 의미하며, 조건 3은 최종적으로 \(w\)가 우리가 원하는 확률 분포가 된다는 것을 암시합니다. 처음에는 \( g = f^i, w = 0 \)으로 하겠습니다. 그러면 위 조건을 모두 만족한다는 것은 쉽게 보일 수 있습니다.
이제 수학적 귀납법을 사용하여 어느 순간까지는 위 조건이 계속 만족했다고 하죠. 만약 어느 간선 \(e\)에 대해 \(g_e > 0\)이라면, 앞에서 \(f^i\)에 순환이 없었다고 가정하였으므로 조건 2에 의해서 분명 \(g\)의 값이 0보다 큰 간선만 가지고도 \( s_i \)에서 \(t_i\)를 향하는 경로가 존재한다는 의미입니다. 그중 경로 하나를 아무거나 고르고 이를 \(P\)라고 부르겠습니다. \(P\) 위의 경로 중 가장 작은 \(g\) 값을 \(x\)라고 하겠습니다. 즉, \( x := \min_{e \in P} g_e > 0 \)입니다. 이제 \(g\)와 \(w\)를 다음과 같이 업데이트 합시다.
- \(P\) 위의 간선 \(e\)에 대해, \( g_e \gets g_e - x \)로 업데이트한다. 나머지 간선은 그대로이다.
- \( w(P) \gets w(P) + x \)로 업데이트한다.
임의의 간선에 대해 \(x > 0\)이고 \(g\)가 감소하기만 하므로 \( g_e \leq f^i_e \)는 계속 성립합니다. 또한 우리는 \( P \) 위의 가장 작은 \(g\) 값을 가지고 왔으므로 \( g_e \geq 0 \)도 만족합니다. 따라서 조건 1이 계속 성립한다는 것을 보일 수 있죠. 또한, \(P\)는 경로이기 때문에 \(s_i\)와 \(t_i\)를 제외한 \(P\) 상의 모든 정점 \(v\)에 대해 조건 2가 성립한다는 것도 알 수 있습니다. 마지막 조건은 위 업데이트를 잘 따져보면 쉽게 유도할 수 있습니다.
매번 \(x > 0\)이므로 언젠간은 \(g_e = 0\)이 되어 위 작업이 끝나게 됩니다. 더하여 위 작업을 한 번 진행할 때마다 최소한 하나의 간선은 \(g\)의 값이 0이 되고, 이후에 값이 다시 증가하지도 않기 때문에 위 작업을 진행하는 횟수도 최대 간선의 개수 \( |E| \)를 넘지 못합니다. 다시 말해, \(w\)에서 0보다 큰 값을 갖는 \( P \)의 개수도 \(|E|\)를 넘지 못합니다.
위 작업이 완료된 후의 \(w\)가 우리가 원하는 \( \mathcal{D}_i \)입니다. 조건 3에 의해 \(f^i\)가 간선에 대한 \(w\)의 주변 분포를 형성한다는 것을 알 수 있습니다. 서포트의 크기도 \(|E|\)를 넘지 않는다는 것도 바로 전의 논의에서 얻을 수 있죠. 따라서 \( \sum_{P \in \mathcal{P}_i} w(P) = 1 \)인지를 보이면 모든 증명이 완료됩니다. 맨 처음에 우리는 \(f^i_e\)가 0보다 큰 간선으로 이루어진 서브그래프에 순환이 없다고 가정하였습니다. 이는 \( s_i \)로 들어오는 간선 \(e \in \delta^-(s_i)\) 중에는 \( f^i_e \)가 0보다 큰 것이 없다는 뜻입니다. 또, 우리는 매 단계마다 \(s_i\)에서 \(t_i\)로 가는 경로를 하나씩 찾아 \(w\)를 증가시켰습니다. 따라서 모든 작업이 완료된 후에는 정확히 \(\sum_{e \in \delta^+(s_i)} f^i_e = 1\)만큼이 증가되었을 것입니다. 이것으로 모든 증명이 완성됩니다. ■
알고리즘
선형 계획법과 정리 1을 활용하여 다음과 같은 알고리즘을 구성해 보도록 하겠습니다.
알고리즘 1. A randomized approximation for multicommodity integral flows
입력: 방향이 있는 그래프 \(G = (V, E)\), 정점 쌍 \( (s_1, t_1), \cdots, (s_k, t_k) \)
출력: 경로의 집합 \( P_1, \cdots, P_k \)
- 완화된 선형 계획법 문제를 푼다. 최적해를 \(f\)라고 한다.
- 정리 1에서 제시된 대로 각 \(i = 1, \cdots, k\)에 대해 \(f_i\)를 간선에 대한 주변 분포로 하는 \( \mathcal{P}_i \) 위의 확률 분포 \( \mathcal{D}_i \)를 만든다.
- 각 사용자 \(i\)마다 독립적으로 \( \mathcal{D}_i \)에서 \( P_i \)를 추출한다.
- \( P_1, \cdots, P_k \)를 반환한다.
앞에서 논의한 것을 바탕으로 위 알고리즘이 다항 시간에 동작한다는 것을 쉽게 보일 수 있습니다. 먼저 단계 1은 다항 시간에 동작한다고 위 절에서 말씀드렸습니다. 또한 정리 2의 증명에서 \( \mathcal{D}_i \)를 만드는 방법도 다항 시간에 충분히 할 수 있습니다. 게다가 \( \mathcal{D}_i \)의 서포트도 다항 크기이므로 단계 3도 다항 시간에 얻을 수 있습니다.
불의 부등식과 체르노프 부등식
위 알고리즘은 각 \( \mathcal{D}_i \)에서 어떤 \( P_i \)를 샘플하냐에 따라 알고리즘의 출력이 달라지는 확률 알고리즘(randomized algorithm)입니다. 이 절에서는 우리 알고리즘을 분석하는데 요긴하게 활용될 여러 부등식을 소개하겠습니다.
첫 번째는 불의 부등식(Boole's inequality)입니다. 이는 union bound라는 이름으로도 잘 알려져 있는데요. 여러 개의 사건 중 하나라도 일어날 확률은 각 사건이 일어날 확률의 합보다는 작거나 같다는 것을 알려줍니다. 어찌 보면 매우 당연한 얘기를 하고 있는데요. 그 증명은 생략하도록 하겠습니다.
정리 2. 불의 부등식
임의의 사건 \( \mathcal{E}_1, \cdots, \mathcal{E}_t \)가 주어졌을 때 이들 중 하나라도 일어날 확률은 각 사건이 일어날 확률의 합보다는 크지 않다. 다시 말해, \[ Pr \left[ \bigvee_{i = 1}^t \mathcal{E}_i \right] = \sum_{i = 1}^t Pr[\mathcal{E}_i] \]를 항상 만족한다.
다음 정리는 체르노프 부등식(Chernoff bound)입니다. 얼핏 보기에는 복잡해 보이지만, 부등식이 의미하는 바는 생각 외로 간단합니다. 바로 어떤 확률 분포든 평균에서 먼 사건은 일어날 확률이 적다는 것이죠. 이는 어떤 분포든, 그것의 확률 밀도 함수(probability density function)를 그려보면 직관적으로 이해할 수 있습니다.
정리 3. 체르노프 부등식
0 아니면 1의 값을 갖는 서로 독립인 (동일할 필요는 없는) 확률 변수 \(X_1, \cdots, X_t\)가 주어졌다고 하자. 이때, \( X = \sum_{i = 1}^t X_t \)가 \( \mathbb{E}[X] \leq U \)를 만족한다고 할 때, 임의의 \( \delta > 1 \)에 대해, \[ Pr [ X \geq \delta U ] < \left( \frac{e}{\delta} \right)^{\delta U} \]를 만족한다.
증명이 궁금하신 분은 다음 글을 참조하시기 바랍니다.
2020/11/14 - [수학적 도구/Basic] - 체르노프 부등식 (Chernoff Bounds)
체르노프 부등식 (Chernoff Bounds)
여러분의 눈 앞에 총 \(n\)개의 서로 다른 상자가 놓여 있다고 합시다. 각 상자 안에는 흰 공과 검은 공으로만 차 있습니다. 여러분은 각 상자의 흰 공과 검은 공의 비율이 얼마나 되는지 모두 알
gazelle-and-cs.tistory.com
분석
이제 알고리즘을 분석할 수 있는 도구가 모두 갖추어 졌습니다. 알고리즘 1에서 \(P_i\)가 어떤 간선 \(e\)를 사용한 것을 나타내는 지시 변수(indicator variable)을 \(X^i_e\)라고 하겠습니다. 즉, 만약 \(P_i\)가 \(e\)를 지나면 \( X^i_e = 1 \)이고, 그렇지 않으면 \( X^i_e = 0 \)이 됩니다. 그러면 \( Y_e := \sum_{i = 1}^k X^i_e \)는 간선 \(e\)를 지나는 경로의 개수를 나타냅니다. 이제 이번 포스트에서 가장 중요한 정리를 증명해 보도록 하죠. 아래에서 \(n := |V|\)은 정점의 개수를 의미합니다.
정리 4. 어떤 간선에 많은 경로가 지날 확률의 상한
임의의 간선 \(e \in E\)에 대해, 높은 확률로 \( Y_e \leq O(\frac{\log n}{\log \log n}) W^\star_\mathsf{IP} \)를 만족한다. 좀 더 엄밀히 말해서 임의의 상수 \(d\)에 대해, 충분히 큰 \(n\)에 대해서 \[ Pr[ Y_e > \delta W^\star_\mathsf{IP} ] < \frac{1}{n^d} \]를 만족하는 \( \delta = O(\frac{\log n}{\log \log n}) \)이 존재한다.
[증명] 먼저 \( E[Y_e] \leq W^\star_\mathsf{IP} \)임을 보이도록 하겠습니다. 이는 다음과 같이 유도됩니다.
\[ E[Y_e] = \sum_{i = 1}^k E[X^i_e] = \sum_{i = 1}^k Pr[e \in P_i] = \sum_{i = 1}^k f^i_e \leq W^\star_\mathsf{LP} \leq W^\star_\mathsf{IP} \]
첫 번째 등식은 기댓값의 선형성(linearity of expectation), 두 번째 등식은 지시 변수의 정의, 세 번째 등식은 정리 1을 통해 이끌어 낼 수 있습니다. 다음 두 부등식은 각각 선형 계획법 문제의 제약 조건(식 1)과 선형 계획법 완화의 특징(식 2)을 통해 얻을 수 있습니다.
이제 \(n\)을 \(e^{e^3} \approx 528491311\)보다 큰 수로 가정하겠습니다. 또, \(c > \frac{10}{3}d\)에 대해, \( \delta = c \frac{\ln n}{\ln \ln n} \)라고 하고, 마지막으로 \( U = W^\star_\mathsf{IP} \)로 두겠습니다. 그러면, 체르노프 부등식(정리 3)에 의해,
\[ Pr[Y_e > \delta W^\star_\mathsf{IP}] < \left(\frac{e}{\delta}\right)^{\delta U} \]
임을 알 수 있습니다. 따라서,
\[ \left( \frac{e}{\delta} \right)^{\delta U} < n^{-d} \]
가 성립함을 보이면 모든 증명이 완성됩니다. 양변 모두 양수이므로 양변에 자연 로그를 취해도 부등호 방향에 변화가 없습니다. 이를 정리하면 다음과 같이 됩니다.
\[ \delta U (\ln e - \ln \delta) < -d \ln n \Rightarrow U \delta \ln \delta - U \delta - d \ln n > 0 \tag{3} \]
이제 좌변이 실지로 0보다 큰지를 살펴보겠습니다. 먼저, \(\delta = c \frac{\ln n}{\ln \ln n} \)을 대입한 후 정리하면,
\[ cU \frac{\ln n}{\ln \ln n} (\ln \ln n - \ln \ln \ln n) - cU \frac{\ln n}{\ln \ln n} - d \ln n \]
이 되고, 이를 한 번 더 다시 쓰면,
\[ (cU - cU \frac{\ln \ln \ln n}{\ln \ln n} - cU \frac{1}{\ln \ln n} - d) \ln n \tag{4} \]
를 얻을 수 있습니다. 여기서 \( n > e^{e^3} \)이라고 하였으므로 우리는
\[ \frac{\ln \ln \ln n}{ \ln \ln n } < \frac{\ln 3}{3}, \quad \frac{1}{\ln n} < \frac{1}{3} \]
이라는 사실을 보일 수 있습니다. 따라서 식 4는
\[ (cU - \frac{1 + \ln 3}{3} c U - d) \ln n > (0.3 c U - d) \ln n > 0\]
을 넘지 않습니다. 이때 첫 번째 부등식은 \( \frac{1 + \ln 3}{3} < 0.7 \)이어서 성립합니다. 마지막 부등식은 \( c > \frac{10}{3} d \)로 잡았고, \( U = W^\star_\mathsf{IP} \geq 1 \)은 자명하므로 이끌어 낼 수 있습니다. 따라서 식 3이 성립한다는 것을 보일 수 있습니다. ■
이것으로 알고리즘 1의 근사비를 계산할 수 있습니다.
정리 5. 알고리즘 1의 근사비
충분히 큰 \(n\)에 대해 높은 확률로 알고리즘 1은 \( O(\frac{\log n}{\log \log n}) \)의 근사비를 갖는다.
[증명] 정리 4에서의 \( \delta, U, d \)를 모두 가지고 오겠습니다. 임의의 간선 \(e \in E\)에 대해, \(Y_e > \delta U\)가 일어나는 사건을 \( \mathcal{E}_e \)라고 부르겠습니다. 그러면 모든 간선 중 적어도 하나의 간선에 대해 위 사건이 일어날 확률은
\[ Pr \left[ \bigvee_{e \in E} \mathcal{E}_e \right] \leq \sum_{e \in E} Pr[ \mathcal{E}_e ] \leq n^{2 - d} \]
이 됩니다. 여기서 첫 번째 부등식은 불의 부등식(정리 2)에 의해, 두 번째 부등식은 \(G\)에 루프나 평행 간선이 없다는 가정으로부터 유도됩니다. 마지막 부등식은 정리 4를 통해 얻을 수 있습니다. 만약 \(d\)의 크기가 충분히 크다면 위 사건은 거의 일어나지 않을 것입니다. ■
마치며
이것으로 다품종 정수 흐름 문제를 근사적으로 해결하는 방법에 대해서 알아보았습니다. 많은 경우 알고리즘에 확률이 가미되면 성능이 좋아지게 됩니다. 또, 요새 느끼는 것이지만, 이를 분석하는 방법도 매우 아름답다고 생각합니다. 포스팅하고 싶은 여러 확률 알고리즘이 있으니 차근히 정리해 보도록 하겠습니다. 체르노프 부등식은 그중에서도 가장 널리 요긴하게 사용되는 방법입니다. 기회가 되면 체르노프 부등식 자체에 대해서도 포스팅해 보도록 하겠습니다.
글에 잘못된 점이 있거나 궁금하신 점이 있으시면 알려주시기 바랍니다. 고맙습니다. :)
참조
[1] Shimon Even, Alon Itai, and Adi Shamir. "On the complexity of time table and multi-commodity flow problems." In 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pp. 184-193. IEEE, 1975.
[2] David P. Williamson and David B. Shmoys. The design of approximation algorithms. Cambridge university press, 2011.