온라인 이분 매칭 경쟁비 상한 (Upper Bound of Competitive Ratio for Online Bipartite Matching)

사진: Unsplash 의 Drew Beamer

지난 시간에 우리는 온라인 분수 이분 매칭 문제(online fractional bipartite matching problem)를 \(1-1/e \approx 0.632\)의 경쟁비로 해결하는 결정론적 알고리즘(deterministic algorithm)인 물 채우기 알고리즘(water-filling algorithm)을 공부하였습니다.

온라인 분수 이분 매칭 (Online Fractional Bipartite Matching)

아래 본문의 정의와 기호는 이전 글의 것과 동일하니 본문을 읽을 때 참고하시기 바랍니다.

 

이제 컴퓨터과학도들에게 남은 질문은 하나죠. 과연 이보다 더 좋은 경쟁비를 갖는 알고리즘을 만들 수 있을까요? 이번 시간에는 온라인 분수 이분 매칭 문제를 해결하는 어떠한 결정론적 알고리즘도 \(1-1/e\)보다 더 좋은 경쟁비를 가질 수 없음을 알아보겠습니다.

정리 1. 온라인 분수 이분 매칭 경쟁비 상한

---

온라인 분수 이분 매칭 문제를 해결하는 어떠한 결정론적 알고리즘도 \(1-1/e\)보다 좋은 경쟁비를 가질 수 없다.

 

그 전에 한 가지 짚고 넘어가야 할 부분이 있습니다. 과연 랜덤 알고리즘(randomized algorithm)은 어떨까요? 온라인 정수 이분 매칭 문제(online integral bipartite matching problem)에서는 결정론적 알고리즘과 랜덤 알고리즘 사이에 경쟁비 차이가 존재했습니다. 전자는 \(1/2\)를 넘을 수 없지만, 후자의 경우에는 랭킹 알고리즘(ranking algorithm)이 \(1-1/e\)의 경쟁비를 가집니다. 온라인 분수 이분 매칭 문제에서도 결정론적 알고리즘과 랜덤 알고리즘 사이에 경쟁비 차이가 존재할까요? 그렇지 않습니다.

정리 2. 결정론적 알고리즘과 랜덤 알고리즘의 경쟁비 차이

---

온라인 분수 이분 매칭 문제를 \(\rho\)의 경쟁비로 해결하는 랜덤 알고리즘 \(\mathcal{A}\)가 있다고 하자. 그러면 해당 문제를 동일한 경쟁비 \(\rho\)로 해결하는 결정론적 알고리즘이 존재한다.

[증명] 각 간선 \(e \in E\)에 대해, \(\mathcal{A}\)가 해당 간선을 따라 할당하는 양을 확률 변수 \(X_e\)라고 하겠습니다. 이 알고리즘의 어떠한 실현(realization)에서도 문제의 제약 조건(constraint)은 만족해야 하므로, 어떤 작업 \(j \in R\)가 도착했을 때, \(\{X_e\}_{e \in \delta(j)}\)를 정한 후에는 이 값을 바꾸지 않으며, \[ \forall i \in L, \; \sum_{e \in \delta(i)} X_e \leq 1, \quad \forall j \in R, \; \sum_{e \in \delta(j)} X_e \leq 1  \]도 만족해야 합니다.

 

이제 작업 \(j \in R\)가 도착했을 때, 각 간선 \(e \in \delta(j)\)마다 \(X_e\)의 기댓값 \(\mathbb{E}[X_e]\)를 할당하는 알고리즘 \(\mathcal{B}\)를 생각해 보겠습니다. 앞에서 \(\mathcal{A}\)가 \(\{X_e\}_{e \in \delta(j)}\)를 정한 후에는 값을 변경하지 않는다고 하였으므로 \(\{ \mathbb{E} [X_e] \}_{e \in \delta(j)}\)도 값이 정해진 후에는 바뀌지 않습니다. 따라서 \(\mathcal{B}\)는 결정론적 알고리즘입니다. 기댓값의 선형성(linearity of expectation)에 의해, \[ \forall i \in L, \; \sum_{e \in \delta(i)} \mathbb{E}[X_e] = \mathbb{E}\left[ \sum_{e \in \delta(i)} X_e \right] \leq 1, \quad \forall j \in R, \; \sum_{e \in \delta(j)} \mathbb{E}[X_e] = \mathbb{E}\left[ \sum_{e \in \delta(j)} X_e \right] \leq 1 \]를 만족하므로 \(\mathcal{B}\)의 출력은 가능한 해입니다. \(\mathcal{A}\)가 출력하는 해의 크기의 기댓값은 \[ \mathbb{E}\left[ \sum_{e \in E} X_e \right] = \sum_{e \in E} \mathbb{E} [ X_e] \]로 \(\mathcal{B}\)가 출력하는 해의 크기와 동일합니다. 등식은 기댓값의 선형성에서 이끌어 내었습니다. 임의의 입력에 대해 위 분석이 성립하므로 \(\mathcal{A}\)의 경쟁비는 \(\mathcal{B}\)의 경쟁비와 같아야 합니다. ■

 

그러므로 온라인 분수 이분 매칭 문제에서는 결정론적 알고리즘의 경쟁비 상한이 곧 랜덤 알고리즘의 경쟁비 상한이 됩니다. 더구나 온라인 정수 이분 매칭 문제는 분수 문제의 특수한 경우에 해당하므로 본문에서 보일 경쟁비 상한이 곧 정수 문제의 경쟁비 상한도 될 수 있습니다. 다시 말해, 이는 지난 시간에 공부했던 랭킹 알고리즘이 최선의 경쟁비를 갖는 알고리즘이라는 점을 의미합니다.

---

증명에 바로 들어가기 전에 먼저 물 채우기 알고리즘이 \(1-1/e\)보다 좋은 경쟁비를 가질 수 없음을 보이도록 하겠습니다. 이 명제가 곧장 정리 1을 의미하는 것은 아닙니다만, 정리 1을 증명할 때 유용한 아이디어를 많이 제공하여 줍니다.

 

어떤 자연수 \(n\)에 대해, 다음과 같은 이분 그래프 \((L \cup R, E)\)를 정의하겠습니다.

• \(L := \{1, 2, \ldots, n\} \)
• \(R := \{1, 2, \ldots, n\} \)
• \(E := \{ (i, j) \mid i + j \leq n + 1 \} \)

예를 들어, \(n = 4\)일 때 이 그래프의 인접 행렬(incidence matrix)을 적어 보자면 아래와 같습니다. 각 행은 기계 정점 \(L\)에 대응하고, 각 열은 기계 정점 \(R\)에 대응합니다.

\(L\) \ \(R\)	1	2	3	4
1	1	1	1	1
2	1	1	1	-
3	1	1	-	-
4	1	-	-	-

그림 1. \(n = 4\)일 때 그래프의 모습. \(L\) 정점들의 순서가 뒤집혀 있는 것에 유의하라.

위 예시에서 유추할 수 있듯이 일반적으로 이 그래프는 \(n \times n\) 정사각 행렬의 위쪽 삼각형 부분이 간선으로 연결된 그래프입니다. 이 그래프에는 완벽 매칭(perfect matching)이 하나 유일하게 존재합니다.

 

이 그래프에서 \(R\)의 각 작업 정점들이 오름차순으로 하나씩 도착하는 입력을 생각해 봅시다. 과연 이 입력에 대해 물 채우기 알고리즘은 어떻게 동작할까요? \(R\)의 첫 번째 작업 정점이 도착했다고 하겠습니다. 이 정점은 \(L = \{1, 2, \ldots, n\}\)의 모든 기계 정점과 인접합니다. 따라서 모든 정점에 \(\frac{1}{n}\)만큼씩 할당할 것입니다. 다음으로 두 번째 작업 정점은 \(\{1, 2, \ldots, n-1\}\)의 기계 정점들과 인접합니다. 현재까지 모든 기계에는 \(\frac{1}{n}\)씩 할당이 되어 있으므로, \(n\)이 충분히 크다면 두 번째 작업 정점은 \(\{1, 2, \ldots, n-1\}\) 각각에 \(\frac{1}{n-1}\) 조각을 할당할 것입니다. 작업을 할당한 후 \(\{1, 2, \ldots, n-1\}\)은 모두 동일하게 \(\frac{1}{n} + \frac{1}{n - 1}\)을 할당받은 상태입니다. 이런 방식으로 우리는 \(j\) 번째 작업 정점이 도착했을 때, 이 정점이 인접한 \(\{1, 2, \ldots, n + 1 - j\}\)가 모두 동일한 부하를 받고 있으며, 따라서 알고리즘은 이 정점들에 \(\frac{1}{n + 1 -j}\)만큼의 작업 조각을 할당할 것임을 유추할 수 있습니다.

 

하지만 위 행동을 모든 작업 정점들에 대해서 해 줄수는 없습니다. 각 기계 정점은 최대 1의 작업을 할당받을 수 있기 때문입니다. 인접한 기계 정점들에 \(\frac{1}{n+1-j}\)의 작업 조각을 온전히 할당한 마지막 작업을 \(\tau \in R\)이라고 부르겠습니다. 그러면 물 채우기 알고리즘이 출력하는 해는 아래와 같을 것입니다.

\(L\) \ \(R\)	1	2	\(\cdots\)	\(\tau\)	\(\tau+1\)	\(\tau+2\)	\(\cdots\)	\(n\)
1	\(\frac{1}{n}\)	\(\frac{1}{n-1}\)	\(\cdots\)	\(\frac{1}{n+1-\tau}\)	\(\varepsilon\)	0	\(\cdots\)	0
2	\(\frac{1}{n}\)	\(\frac{1}{n-1}\)	\(\cdots\)	\(\frac{1}{n+1-\tau}\)	\(\varepsilon\)	0	\(\cdots\)	-
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\cdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\cdots\)	\(\vdots\)
\(n - \tau\)	\(\frac{1}{n}\)	\(\frac{1}{n-1}\)	\(\cdots\)	\(\frac{1}{n+1-\tau}\)	\(\varepsilon\)	-	\(\cdots\)	-
\(n - \tau +1\)	\(\frac{1}{n}\)	\(\frac{1}{n-1}\)	\(\cdots\)	\(\frac{1}{n+1-\tau}\)	-	-	\(\cdots\)	-
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\cdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\cdots\)	\(\vdots\)
\(n\)	\(\frac{1}{n}\)	-	\(\cdots\)	-	-	-	\(\cdots\)	-

 

우리는 \(\tau\)의 값을 계산할 수 있습니다. \((\tau + 1)\) 번째 작업부터 물 채우기 알고리즘이 기계들에 작업을 제대로 할당할 수 없는 이유는 그때까지 할당된 부하가 \[ \frac{1}{n} + \frac{1}{n - 1} + \cdots + \frac{1}{n + 1 - \tau} \approx 1 \tag{1}\]이기 때문입니다. 어떤 자연수 \(k\)에 대해, \(k\) 번째 조화수(\(k\)-th harmonic number)는 \( H_k = 1 + \frac{1}{2} + \cdots + \frac{1}{k} \)로 정의되며, \( H_k \approx \ln k \)임은 잘 알려진 사실입니다. 이를 활용하여 식 (1)을 정리하면, \[ 1 \approx H_n - H_{n - \tau} \approx \ln n - \ln (n-\tau) = \ln \left( \frac{n}{n - \tau} \right) \]을 이끌어낼 수 있습니다. 이를 정리하면, \[ \tau \approx n \left( 1-\frac{1}{e} \right) \]를 얻을 수 있습니다.

 

앞에서 \(\tau\)는 인접한 기계에 \(\frac{1}{n + 1 -j}\)를 온전히 할당할 수 있는 마지막 작업으로 정의하였습니다. 다시 말해, \(\tau\) 번째 작업까지는 매번 1의 작업을 모두 기계에 할당할 수 있지만, \((\tau + 1)\) 번째 작업을 처리하면 \(\{1, 2, \ldots, n - \tau\}\)의 모든 기계가 1의 작업량을 채운 상태가 됩니다. 이후의 작업은 \( \{1, 2, \ldots, n - \tau\} \)의 기계에만 할당이 가능하므로 전혀 할당할 수 없습니다. 따라서 물 채우기 알고리즘은 이 입력에서 최대 총 \(\tau + 1 \approx n \left( 1 - \frac{1}{e}\right) + 1\)만큼의 작업을 할당할 수 있습니다. 이 그래프에는 완벽 매칭이 존재하므로, \(n\)이 충분히 클 때, 물 채우기 알고리즘은 이 입력에서 \(1 - 1/e\)의 경쟁비를 갖습니다.

---

이제부터 정리 1을 증명해 보겠습니다.

정리 1. 온라인 분수 이분 매칭 경쟁비 상한

---

온라인 분수 이분 매칭 문제를 해결하는 어떠한 결정론적 알고리즘도 \(1-1/e\)보다 좋은 경쟁비를 가질 수 없다.

결정론적 알고리즘을 고려하므로 알고리즘의 동작을 망가뜨리는 적절한 적응형 상대방(adaptive adversary)을 제시하는 것이 증명의 핵심입니다.

 

앞에서 우리는 물 채우기 알고리즘의 경쟁비 상한을 주는 입력을 보았습니다. 그러한 결과가 나오게 된 이유를 한 마디로 써 보자면, 전체 입력에는 완벽 매칭이 하나 유일하게 존재하지만 물 채우기 알고리즘은 매번 인접한 기계에 균등하게 할당을 하다 보니 완벽 매칭의 간선을 따라서는 그다지 할당하지 않기 때문입니다. 이 아이디어를 임의의 결정론적 알고리즘을 상대하는 적응형 상대방을 구성하는 데 적용해 보도록 하겠습니다.

 

어떤 자연수 \(n\)에 대해 다음의 적응형 상대방을 생각해 봅시다. 상대방은 처음에 알고리즘에 기계가 \(n\) 개 있다고 알려 줍니다. 각 기계는 \(L := \{1, 2, \ldots, n\}\) 중에서 하나의 이름을 가지나, 아직은 어느 기계가 어느 이름인지는 정하지 않은 상태입니다. 차후에 알고리즘이 어떻게 동작하는지에 따라 각 기계에 이름을 하나씩 붙여 줄 예정입니다. 상대방은 총 \(n\) 개의 작업 \(R := \{1, 2, \ldots, n\}\)을 제시할 예정입니다.

 

상대방은 첫 번째 작업으로 모든 기계와 인접한 작업을 알고리즘에 제시합니다. 알고리즘이 각 기계 \(i\)에 \(x_{i,1}\)만큼 할당했다고 해 보겠습니다. 일단 하나의 작업이 할당되었으므로, \[ \sum_{i = 1}^n x_{i, 1} \leq 1 \]을 만족해야 합니다. \( \{x_{i, 1}\}_{i = 1, \ldots, n} \) 중에서 가장 작은 값을 갖는 \(i\)를 \(n\)이라고 이름을 붙여 주겠습니다. 그러면 비둘기집 원리(pigeonhole principle)에 의해, \[ x_{n,1} \leq \frac{\sum_{i' = 1}^n x_{i',1}}{n} \iff (n-1) x_{n, 1} \leq \sum_{i'=1}^{n-1} x_{i',1} \]을 만족해야 합니다.

 

이제 두 번째 작업을 살펴 봅시다. 이번에 상대방은 첫 번째 작업을 처리하면서 정해진 \(n\)을 제외한 나머지 기계들, 즉, \( \{1, \ldots, n-1\} \)의 기계들이랑만 인접한 작업을 제시합니다. 알고리즘이 각 기계 \(i\)에 \( x_{i, 2} \)씩 할당했다고 하겠습니다. 최대 총 1의 작업을 할당할 것이므로 \[ \sum_{i = 1}^{n-1} x_{i, 2} \leq 1\]을 만족합니다. 이번에는 기계 \(n-1\)을 정할 차례입니다. 이는 \( \{x_{i, 1} + x_{i, 2}\}_{i = 1, \ldots, n-1} \) 중에서 가장 작은 값을 갖는 기계로 정하겠습니다. 같은 원리로 \[ x_{n-1, 1} + x_{n-1, 2} \leq \frac{\sum_{i' = 1}^{n-1} x_{i', 1} + x_{i, 2} }{n-1} \iff (n-2) \sum_{j' = 1}^2 x_{n-1, j'} \leq \sum_{i'=1}^{n-2} \sum_{j'=1}^2 x_{i', j'} \]을 만족할 것입니다.

 

이 작업을 일반화하면, 임의의 \(j = 1, \ldots, n\)에 대해, 상대방은 \(j\) 번째 도착하는 작업을 \( \{1, \ldots, n - j + 1\} \)의 기계와만 인접하도록 알고리즘에 제시할 것입니다. 알고리즘이 \( \{x_{i, j}\}_{i = 1, \ldots, n - j + 1} \)씩을 각 인접한 기계에 할당했다고 해 보겠습니다. 그러면 \[ \sum_{i = 1}^{n - j + 1} x_{i, j} \leq 1 \tag{2} \]을 만족합니다. 또한 \( \{ \sum_{j'=1}^{j} x_{i, j} \}_{i = 1, \ldots, n - j + 1} \) 중에서 가장 작은 값을 갖는 기계를 \(n - j + 1\)이라고 이름을 붙여줄 것입니다. 앞에서와 같이 비둘기집 원리에 의해, \[ \sum_{j'=1}^j x_{n-j+1, j'} \leq \frac{\sum_{i'=1}^{n-j+1} \sum_{j'=1}^j x_{i', j'} }{n-j+1} \iff (n-j) \sum_{j'=1}^j x_{n-j+1, j'} \leq \sum_{i'=1}^{n-j} \sum_{j'=1}^j x_{i',j'} \tag{3} \]이 성립해야 합니다.

 

상대방이 모든 작업을 제시한 후에는 모든 기계의 이름이 붙은 상태가 될 것입니다. 또한 각 기계 \(i \in \{1, \ldots, n\}\)은 정확히 \( \{1, \ldots, n - i + 1\} \)의 작업과 인접할 것입니다. 각 기계에 걸리는 부하도 1을 넘을 수 없으므로, \[ \sum_{j = 1}^{n-i+1} x_{i, j} \leq 1 \tag{4} \]을 만족해야 합니다. 알고리즘이 할당한 작업의 총량은 \[ \sum_{(i, j) : i + j \leq n + 1} x_{i, j} \tag{5} \]와 동일합니다. 표현의 편의를 위해 위에서와 같이 \(E := \{(i, j) \mid i + j \leq n + 1\}\)로 표기하겠습니다.

 

위 과정을 통해 얻은 그래프는 물 채우기 알고리즘의 경쟁비 상한을 구할 때 사용한 그래프와 동일하다는 것을 확인하시기 바랍니다. 따라서 이 그래프에는 유일한 완벽 매칭이 존재합니다. 이제 남은 것은 알고리즘이 위에서 논의한 조건 (2), (3), (4)를 모두 만족하면서 식 (5)의 값이 얼마나 커질 수 있는지를 분석하는 것입니다. 이를 일목요연하게 적어 보면, 아래의 최적화 문제로 나타낼 수 있습니다.

\[ \begin{array}{lll} \text{maximize } & \displaystyle \sum_{(i, j) \in E} x_{i, j} \\ \text{subject to } & \displaystyle \sum_{j = 1}^{n - i + 1} x_{i, j} \leq 1, & \forall i \in L, \\ & \displaystyle \sum_{i = 1}^{n - j + 1} x_{i, j} \leq 1, & \forall j \in R, \\ & \displaystyle (n-j) \sum_{j'=1}^j x_{n-j+1, j'} \leq \sum_{i'=1}^{n-j} \sum_{j'=1}^j x_{i', j'}, & \forall j \in R, \\ & x_{i, j} \geq 0, & \forall (i, j) \in E. \end{array} \tag{P} \]

이 최적화 문제는 선형 계획법(linear programming, LP)입니다. 분석적으로 최대화 LP의 상한을 구하는 방법은 그것의 쌍대 문제(dual program)에 가능한 해(feasible solution)를 얻는 것입니다. LP 쌍대성과 관련하여는 아래 글을 참고하시기 바랍니다.

[선형 계획법] 쌍대성(Duality)

 

LP (P)의 첫 번째 제약 조건에 해당하는 변수를 \(\alpha_i\), 두 번째에 해당하는 변수를 \(\beta_j\), 세 번째에 해당하는 변수를 \(\gamma_j\)라고 하겠습니다. 그러면 LP (P)의 쌍대 문제는 다음과 같습니다.

\[ \begin{array}{lll} \text{minimize } & \displaystyle \sum_{i \in L} \alpha_i + \sum_{j \in R} \beta_j \\ \text{subject to } & \displaystyle \alpha_i + \beta_j + (i - 1) \gamma_{n - i + 1} - \sum_{j'=j}^{n-i} \gamma_{j'} \geq 1, & \forall (i, j) \in E, \\ & \alpha_i, \beta_j, \gamma_j \geq 0, & \forall i \in L, \forall j \in R. \end{array} \tag{D} \]

쌍대 문제의 제약 조건이 어떻게 얻어진 것인지 간단히 설명을 드리겠습니다. 이는 원 문제 (P)의 각 \((i, j) \in E\)에 대해, \(x_{i, j}\)가 (P)의 어느 제약 조건에서 등장하는지를 따져 보면 됩니다. 첫 번째 제약 조건에서는 \(\alpha_i\)가, 두 번째 제약 조건에서는 \(\beta_j\)가 포함되어야 한다는 것은 어렵지 않게 확인할 수 있습니다.

 

세 번째 제약 조건은 다소 복잡해 보입니다만, 알고리즘의 동작을 생각하면 이해하기 편합니다. \((i, j)\)는 \(j\) 번째 작업이 도착했을 때 처음 등장합니다. 또한 기계 \(i\)는 \((n - i + 1)\) 번째 작업을 처리하면서 정해집니다. 그러므로 \(j\) 번째 작업부터 \((n-i)\) 번째 작업까지는 세 번째 제약 조건의 우변에서 등장하여 \(- \gamma_{j'} \)이 포함되어야 하나, \((n - i + 1)\) 번째 작업 때에는 좌변에 등장하므로 \((i-1) \gamma_{n-i+1}\)이 더해져야 합니다. 이후 작업에서는 등장하지 않습니다.

 

이제 우리의 목표는 목적 함숫값이 \(n \left( 1 - \frac{1}{e} \right)\) 정도인  LP (D)에 가능한 해를 찾는 것입니다. 그러면 자연스럽게 LP 쌍대성에 의해 LP (P)의 목적 함수의 최댓값이 \( n \left( 1 - \frac{1}{e} \right) \)를 넘지 않음을 알 수 있고, 이것으로 모든 증명이 완성될 것입니다.

 

LP 쌍대성에는 한 가지 흥미로운 성질이 있습니다. 바로 상호 보완성(complementarity, complementary slackness)인데요. 이는 원 문제의 최적해와 쌍대 문제의 최적해가 동시에 만족해야 하는 필요충분조건입니다. 앞에서 소개한 LP (P)와 LP (D)에 적용해 보자면, \(x\)와 \((\alpha, \beta, \gamma)\)가 각각 (P)와 (D)에 최적해라면,

1. \(\alpha_i \left( 1 - \sum_{j = 1}^{n-i+1} x_{i,j} \right) = 0, \; \forall i \in L\),
2. \(\beta_j \left( 1 - \sum_{i = 1}^{n-i+1} x_{i,j} \right) = 0, \; \forall j \in R\),
3. \( \gamma_j \left( \sum_{i'=1}^{n-j} \sum_{j'=1}^j x_{i', j'} - (n-j) \sum_{j'=1}^j x_{n-j+1, j'} \right) = 0, \; \forall j \in R \),
4. \( x_{i, j} \left( \alpha_i + \beta_j + (i-1) \gamma_{n-j+1} - \sum_{j'=j}^{n-i} \gamma_{j'} - 1 \right) = 0, \; \forall (i, j) \in E \)

를 모두 만족해야 합니다.

 

여기서 한 가지 추측을 해 봅시다. 이 상대방을 상대로 물 채우기 알고리즘의 출력이 최적해가 될 것이라고 말이죠. 앞에서 우리는 이 상대방이 만드는 그래프가 결국 이전 절에서 물 채우기 알고리즘의 경쟁비 상한을 구할 때 사용했던 그래프와 동일하다는 사실을 발견했습니다. 그러므로 물 채우기 알고리즘은 이 상대방을 상대로도 동일한 해를 출력할 것입니다. 이 해에서는 \(\tau\) 번째 작업까지는 인접한 기계에 균등하게 총 1의 작업을 모두 할당했지만, \((\tau + 1)\) 번째 작업부터는 기계가 모두 1의 부하를 받는 상태가 되어 작업을 (거의) 전혀 할당하지 못했습니다.

 

이 해가 최적해라는 가정 아래, 우리는 상호 보완성을 통해 최적의 \((\alpha, \beta, \gamma)\)가 만족해야 하는 성질들을 유추해 볼 수 있습니다.

1. 기계 \(i \geq n - \tau + 1\)는 총 부하가 1이 되지 못하므로,  \(\alpha_i = 0\),
2. \((\tau + 1)\) 번째 이후의 작업 \(j\)는 1의 작업을 모두 할당하지 못하므로, \(\beta_j = 0\),
3. \((\tau + 1)\) 번째 이후 부터는 할당이 (거의) 증가하지 않으므로, \(\gamma_j = 0\),
4. \(j \leq \tau\), \(i \leq n - j + 1\)에 대해서는 \(x_{i, j} > 0\)이므로, \[ \alpha_i + \beta_j + (i - 1) \gamma_{n-i+1} - \sum_{j' = j}^{n - i} \gamma_{j'} = 1. \tag{6} \]

그림 2. 현재 고려하는 상대방을 상대로 물 채우기 알고리즘이 출력하는 해와 이에 상호 보완적으로 대응하는 쌍대해의 도식. 빨간색 빗금으로 표현한 부분은 물 채우기 알고리즘이 1의 작업을 온전히 흘려준 할당에 해당한다.

 

지금까지 발견한 성질들을 활용하여 \((\alpha, \beta, \gamma)\)를 특정해 보도록 하겠습니다. 먼저 동일한 어떤 기계 \(i\)와 두 작업 \(j\)와 \((j + 1)\)에 대해, 각각 식 (6)을 등식으로 만족해야 하므로, \[ \begin{array}{l} \displaystyle \alpha_i + \beta_j + (i - 1) \gamma_{n - i + 1} - \sum_{j' = j}^{n-i} \gamma_{j'} = \alpha_i + \beta_{j + 1} + (i - 1) \gamma_{n-i+1} - \sum_{j' = j+1}^{n-i} \gamma_{j'} \\ \implies \beta_j - \beta_{j + 1} = \gamma_j \end{array}\]를 이끌어 낼 수 있습니다. 이를 통해, 모든 \(j \in R\)에 대해, \[ \beta_j := \sum_{j' = j}^n \gamma_{j'} \tag{7} \]이 적절한 \(\beta_j\)의 정의가 된다는 것을 알 수 있습니다.

 

식 (7)을 식 (6)에 대입하면, \[ \alpha_i + (i-1) \gamma_{n-i+1} + \sum_{j'=n-i+1}^n \gamma_{j'} = 1 \tag{8}\]을 얻을 수 있습니다. 이 식이 오로지 \(i \in L\)에만 의존하고 있다는 것을 확인하시기 바랍니다. 만약 \(i \leq n - \tau\)인 경우, 위 식에 등장하는 \(\gamma_{j'}\)은 모두 \(j' \geq \tau + 1\)이므로, 성질 iii.에 의해 해당 \(\gamma_{j'}\)은 모두 0의 값을 가집니다. 따라서, \(\alpha_i = 1\)이 되어야 하겠습니다. 이것으로 \(\alpha\)는 다음과 같은 모습이어야 함을 알 수 있습니다. \[ \alpha_i = \begin{cases} 1, & \text{ if } i \leq n - \tau, \\ 0, & \text{ if } i \geq n - \tau + 1. \end{cases} \tag{9} \]

 

식 (8)로 다시 돌아와서, 이번에는 \(i \geq n - \tau + 1\)일 때를 생각해 보겠습니다. 이때는 \( \alpha_i = 0 \)의 값을 가집니다. 편의 상 식 (8)에다가 \(j := n-i+1\)로 치환해 보겠습니다. 그러면 \( j \leq \tau \)일 때, \[ (n-j) \gamma_j + \sum_{j'=j}^n \gamma_{j'} = (n - j + 1) \gamma_j + \sum_{j' = j+1}^n \gamma_{j'} = 1 \tag{10} \]을 얻을 수 있습니다. 먼저 \(j = \tau\)일 때, 성질 iii.에 의해 \[ \gamma_\tau = \frac{1}{n-\tau+1} \]이 되어야 한다는 것을 알 수 있습니다.

 

이제, 어떤 \(j\)와 \(j-1\)에 대해, 식 (10)이 등식이 되어야 한다는 조건에 의해, \[ \begin{array}{l} \displaystyle (n-j+1) \gamma_j + \sum_{j'=j+1}^n  \gamma_{j'} = (n-j+2) \gamma_{j-1} + \sum_{j' = j}^n \gamma_{j'} \\ \displaystyle \implies \gamma_{j - 1} = \frac{n-j}{n-j+2} \gamma_j \end{array} \]라는 점화식을 이끌어 낼 수 있습니다. 이 성질을 활용하면, 간단한 수학적 귀납법을 통해 우리는 임의의 \(j \leq \tau\)에 대해, \[ \gamma_j = (n - \tau) \left( \frac{1}{n-j} - \frac{1}{n - j +1} \right) \tag{11} \]이 된다는 것을 보일 수 있습니다.

 

마지막으로 성질 iii., 식 (7), 식(11)을 엮으면, 우리는 \(\beta\)가 다음과 같아야 함을 알 수 있습니다.

\[ \beta_j = \begin{cases} \displaystyle 1 - \frac{n - \tau}{n - j + 1}, & \text{ if } j \leq \tau, \\ 0, & \text{ if } j \geq \tau + 1. \end{cases} \]

 

이것으로 물 채우기 알고리즘의 출력과 상호 보완적이면서 LP (D)에 가능한 \((\alpha, \beta, \gamma)\)를 모두 만들었습니다. 이 쌍대 해의 목적 함숫값은 \[ \sum_{i \in L} \alpha_i + \sum_{j \in R} \beta_j = \sum_{i \leq n - \tau} 1 + \sum_{j \leq \tau} \left(1 - \frac{n - \tau}{n - j + 1} \right) = n - (n - \tau)\sum_{j \leq \tau} \frac{1}{n - j + 1}\]입니다. 우변 마지막 항의 합에 집중해 보겠습니다. 편의 상 \(i := n - j + 1\)로 치환해 보면, \[ \sum_{i = n - \tau + 1}^n \frac{1}{i} \approx \int_{n-\tau}^n \frac{1}{i} di = \ln \frac{n}{n - \tau} \approx 1 \]을 얻을 수 있습니다. 여기서 첫 번째 근사는 \(n\)이 충분히 큰 경우 성립하며, 마지막 근사는 \(\tau \approx n \left( 1 - \frac{1}{e} \right)\)이기 때문에 성립합니다. 따라서 목적 함숫값은 거의 \(n \left( 1 - \frac{1}{e}\right)\)가 된다는 것을 알 수 있습니다. LP 쌍대성에 의해 LP (P)의 목적 함숫값도 \(n \left( 1 - \frac{1}{e} \right)\)를 넘을 수 없습니다.

 

앞에서 우리는 입력 그래프에 완벽 매칭이 존재한다고 했습니다. 반면 충분히 큰 \(n\)에 대해서는 어떤 결정론적 알고리즘이라도 이 적응형 상대방을 상대해서는 최대 \(n \left( 1 - \frac{1}{e}\right)\)만 할당할 수 있습니다. 이로써 정리 1의 증명이 마무리됩니다.

---

이것으로 온라인 분수 이분 매칭 문제를 해결하는 어떤 알고리즘도 \(1 - 1/e\)보다 좋은 경쟁비를 가질 수 없다는 것에 대한 증명을 모두 마칩니다. 이 결과는 분수 문제를 해결하는 물 채우기 알고리즘이 최선의 알고리즘임을 보임과 동시에 정수 문제를 해결하는 랭킹 알고리즘 또한 최선의 알고리즘이라는 사실을 알려 줍니다.

 

사실, 수 년 전에 먼저 증명을 시도해 보려고 했었습니다. 하지만, 당시에는 실력이 미진하여 제대로 증명하지 못하고 그냥 넘어갔었습니다. 이번에 증명에 성공하여 대단히 기쁩니다. 그래도 그동안 허투루 공부하지는 않았다는 생각이 들기도 합니다.

 

본문의 증명은 엄밀하지 않습니다. 특히 \(n\)이 매우 크다는 가정 아래 몇몇 부분들을 뭉개고 넘어 갔습니다. 증명을 엄밀히 적으면 알고리즘의 경쟁비 하한을 \(n\)에 대한 식으로 나타낼 수 있을 것 같습니다. 이와 관련하여는 참고 문헌 [2]를 참고하면 좋겠습니다. 제대로 읽어 보지는 않았습니다만, 특히 흥미로운 부분은, \(n\)이 고정되어 있는 경우, 분수 문제를 푸는 알고리즘의 경쟁비와 정수 문제를 푸는 알고리즘의 경쟁비 사이에 격차가 존재한다는 것입니다. 이는 \(n\)이 매우 큰 경우에 둘 다 \(1-1/e\)로 수렴하는 것과 상반되는 사실로 보여서 흥미롭습니다. 기회가 되면 해당 논문을 읽어서 공유해 보면 좋겠네요.

 

읽어 주셔서 고맙습니다.

참고 문헌

[1] Bobby Kleinberg. Lecture note of CS 6820 Analysis of Algorithms, Cornell University, Fall 2012. [Link]

 

[2] Uriel Feige. "Tighter bounds for online bipartite matching." Building Bridges II: Mathematics of László Lovász. Berlin, Heidelberg: Springer Berlin Heidelberg, 2020. 235-255.