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

사진: Unsplash 의 Miguel A Amutio

우리에게 처리해야 할 작업들이 있다고 해 보겠습니다. 다만 작업들은 처음부터 주어지지 않고 시간이 흐르면서 하나씩 도착합니다. 작업을 처리하기 위해 우리는 최대 하나의 작업을 할당받을 수 있는 기계를 몇 대 갖고 있습니다. 문제는 각 작업마다 해당 작업을 처리할 수 있는 기계가 따로 정해져 있다는 것이며, 심지어 어느 기계에서 처리될 수 있는지는 해당 작업이 도착해야 알 수 있다는 점입니다. 우리는 매번 작업이 도착할 때마다 이 작업을 어떤 기계에 할당할지, 그리고 만약 할당한다면, 어느 가용한 기계에 할당하여 줄지를 바로 결정하여야 합니다. 여기서 어려운 점은 이 결정을 후일 번복할 수 없다는 것입니다. 이런 환경에서 작업이 모두 도착했을 때 최대한 많은 작업을 처리하는 것이 목표입니다. 이는 유명한 온라인 최적화 문제 중 하나인 온라인 이분 매칭 문제(online bipartite matching problem)를 나타낸 것으로, 그동안 저는 제 블로그에서 여러 번 이 문제를 다룬 바 있습니다.

 

그런데 만약 작업을 쪼개어 여러 기계에 할당할 수 있다면 어떻게 될까요? 예를 들어, 어떤 작업이 도착했을 때, 0.2 조각은 첫 번째 기계에, 0.3 조각은 두 번째 기계, 나머지 0.5 조각은 세 번째 기계에 나누어 할당할 수 있는 것입니다. 또한 각 기계는 할당 받은 작업 조각들의 합이 1을 넘지만 않으면 되는 것이고요. 작업을 조각내는 것이 찜찜하다면, 한 작업이 만 개의 동일한 세부 작업으로 이루어져 있고, 각 기계도 최대 만 개의 세부 작업을 할당 받을 수 있는 상황으로 보셔도 무방합니다. 이 문제를 우리는 온라인 분수 이분 매칭 문제(online fractional bipartite matching problem)라고 부릅니다. 구분을 위해 작업을 쪼갤 수 없는 원래 문제는 온라인 정수 이분 매칭 문제(online integral bipartite matching problem)라고도 부릅니다.

 

지난 포스트에서 우리는 온라인 정수 이분 매칭 문제를 해결하는 경쟁 알고리즘들을 공부하였습니다. 특히, 1/2의 경쟁비를 갖는 결정론적 알고리즘과 $1-1/e$의 경쟁비를 갖는 랜덤 알고리즘을 배웠죠. 온라인 분수 이분 매칭 문제에서는 알고리즘이 더 높은 자유를 가지므로 더 좋은 경쟁비의 알고리즘을 기대할 수 있겠습니다. 실지로 이번 포스트에서는 분수 매칭 문제를 $1-1/e$의 경쟁비로 해결하는 결정론적 알고리즘을 소개합니다.

문제 정의

문제의 입력은 어떤 이분 그래프(bipartite graph) $G=(L\cup R,E)$ 위에서 정의됩니다. 편의 상 $L$의 각 정점을 기계, $R$의 각 정점을 작업이라고 부르겠습니다. 만약 어떤 작업 $j\in R$가 어떤 기계 $i\in L$에 할당될 수 있을 때, 두 정점 사이에 간선 $(i,j)\in E$가 존재합니다. 기계는 처음부터 모두 알려지는 반면, 작업은 하나씩 입력됩니다.

 

어떤 작업 $j\in R$가 들어왔을 그때에서야 우리는 $j$가 할당될 수 있는 기계가 무엇인지 알 수 있습니다. 작업 $j$에 인접한(adjacent) 기계를 $N(j)$, 딸린(incident) 간선들을 $\delta (j)$라고 부르겠습니다. 우리는 1의 작업량을 갖는 작업 $j$를 쪼개어 인접한 기계에 나누어 할당해 주려고 합니다. 다시 말해, 인접한 기계 $i\in N(j)$에 할당된 조각의 양을 $x_{(i,j)}$라고 한다면, $$\sum _{e\in \delta (j)}{x}_e\le 1$$을 만족해야 하겠습니다. 이번 작업 $j$에 대해 $\{x_e{\}}_{e\in \delta (j)}$가 결정된 후에는 이 값을 변경할 수 없습니다. 각 기계 또한 도합 최대 1의 작업량을 할당받을 수 있습니다. 따라서 각 $i\in L$에 대해 어느 순간에서든지 $$\sum _{e\in \delta (i)}{x}_e\le 1$$을 만족해야 합니다. 여기서 $\delta (i)$는 앞에서 정의한 것과 유사하게, 기계 $i$에 딸린 간선들을 의미합니다. 우리의 목표는 최대한 많은 양의 작업을 처리하는 것입니다. 이는 각 간선에 할당된 작업 조각의 양을 최대화하는 것과 같습니다.

 

이를 선형 계획법으로 나타내면 아래와 같습니다.

$$\begin{array}{rl}\text{maximize }& {\displaystyle \sum _{e\in E}{x}_e}\\ \text{subject to }& {\displaystyle \sum _{e\in \delta (i)}{x}_e\le 1,}& \mathrm{\forall }i\in L,\\ & {\displaystyle \sum _{e\in \delta (j)}{x}_e\le 1,}& \mathrm{\forall }j\in R,\\ & x_e\ge 0,& \mathrm{\forall }e\in E.\end{array}$$

이 LP를 활용하여 문제를 다시 이해해 보겠습니다. 처음에는 알려진 정점이 없고, 각 기계에 가해진 첫 번째 제약 조건만 존재합니다. 매 시각 어떤 작업 $j$가 들어오면, $\delta (j)$가 알려집니다. 그러면 첫 번째 제약 조건은 해당 변수들이 추가되는 방식으로 갱신되고, 두 번째 제약 조건은 해당 $j$의 것이 통째로 추가되는 방식으로 갱신됩니다. 이때 우리는 다음 작업이 들어오기 전에 $\{x_e{\}}_{e\in \delta (j)}$의 값을 결정해 주어야 합니다. 이 결정은 이후 번복될 수 없습니다.

물 채우기 알고리즘(water-filling algorithm)

이제 알고리즘을 생각해 보겠습니다. 작업을 쪼갤 수 있기 때문에 가장 쉽게 생각할 수 있는 알고리즘은 역시 균등하게 쪼개서 기계에 할당해 주는 방법이겠습니다. 다시 말해, 작업 $j$가 입력되었을 때, 각 $e\in \delta (j)$에 대해, $x_e=1/|N(j)|$로 두는 것이죠. 하지만 이 알고리즘은 1/2보다 좋은 경쟁비를 가질 수 없습니다. 다음의 입력을 생각해 봅시다. 이 입력은 이전 글에서도 사용된 바 있습니다.

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

• $L_1:=\{i_1,\dots ,i_d\}$, $L_2:=\{i_{d+1},\dots ,i_{2d}\}$, $L:=L_1\cup L_2$.
• $R_1:=\{j_1,\dots ,j_d\}$, $R_2:=\{j_{d+1},\dots ,j_{2d}\}$, $R:=R_1\cup R_2$.
• $k\in \{1,\dots ,d\}$에 대해, $N(j_k):=\{i_k\}\cup L_2$.
• $k\in \{d+1,\dots ,2d\}$에 대해, $N(j_k):=\{i_k\}$.
• $R_1$이 모두 입력된 후 $R_2$가 입력된다.

그림 1. $d=3$일 때 입력의 도식.

$R_1$이 모두 들어왔을 때를 생각해 보겠습니다. 이 알고리즘은 각 작업 $j$를 $d+1$ 등분 낸 후 각 기계에 할당하므로, $L_1$의 각 기계는 $\frac{1}{d+1}$씩의 작업 조각을, $L_2$의 각 기계는 $\frac{d}{d+1}$씩의 작업 조각을 할당 받게 됩니다. 따라서 $R_2$의 각 작업들은 자신이 할당될 수 있는 유일한 기계에 최대 $\frac{1}{d+1}$의 작업 조각만 할당시킬 수 있습니다. 그러므로 모든 작업이 도착한 후 알고리즘이 할당시킨 작업의 총합은 $d+\frac{d}{d+1}<d+1$이 됩니다. 최적해에서는 모든 작업을 할당시킬 수 있으므로, 이 알고리즘의 경쟁비는 $\frac{d+1}{2d}\to \frac{1}{2}$을 넘지 못합니다.

 

이러한 상황이 발생한 원인은 무엇일까요? 바로 $L_1$의 기계보다 $L_2$의 기계에 너무 많은 작업을 할당했기 때문입니다. $R_1$의 작업이 들어올 때마다 $L_1$의 기계에는 $\frac{1}{d+1}$의 부하만 생기는데 반해 $L_2$의 기계는 부하가 계속 증가하는 것을 확인하시기 바랍니다. 하지만 알고리즘은 이 현상을 무시하고 $R_1$의 작업을 인접한 기계에 균등하게 분배합니다.

 

따라서 작업을 할당하는 보다 자연스러운 방법은 부하가 적은 기계부터 차곡차곡 작업 조각을 할당하여 인접한 기계들이 최대한 동일한 부하를 받도록 하는 것이겠습니다. 어떻게 하면 이 목표를 달성할 수 있을지 예시와 함께 알아 보겠습니다. 어떤 작업이 하나 도착했을 때를 생각해 봅시다. 이 작업이 할당될 수 있는 기계들의 그동안 할당 받은 작업량이 다음 그림과 같이 주어졌다고 해 보겠습니다.

그림 2. (왼쪽) 어떤 작업이 도착했을 때의 상황. 각 기계의 왼 편에는 그동안 할당 받은 작업량을 나타낸다. (오른쪽) 각 기계가 할당 받은 작업량의 도식.

우리의 목표는 인접한 기계들이 최대한 동일한 부하를 받도록 작업을 할당하는 것입니다. 이를 위해 가장 부하가 적은 기계부터 차츰차츰 작업을 할당시켜 보도록 하겠습니다. 현재 세 번째 기계가 가장 적은 0.05의 작업을 받은 상태이므로 세 번째 기계에다가 작업을 할당해 봅시다. 만약 0.1 조각만큼을 할당한다면 아래와 같은 모습이 될 것입니다.

그림 3. 세 번째 기계에 0.1의 작업 조각을 할당한 경우.

여전히 세 번째 기계가 가장 적은 부하를 받고 있으므로, 세 번째 기계에 계속해서 작업을 할당시켜 보겠습니다. 도합 0.2의 조각이 세 번째 기계에 할당되었을 때를 생각해 보겠습니다.

그림 4. 세 번째 기계에 0.2의 작업 조각을 할당한 경우.

이제 세 번째 기계의 부하가 0.25가 되어 두 번째 기계가 받는 부하와 동일해졌습니다. 여전히 우리는 0.8의 작업 조각이 남아있습니다. 이제부터는 어떻게 작업을 할당해 주는 것이 바람직할까요? 두 번째와 세 번째 기계에 동시에 할당하는 것이 자연스러운 선택일 것입니다. 예를 들어, 이때로부터 두 번째와 세 번째 기계에 0.1씩을 더 할당해 준다면 아래와 같은 모습일 것입니다.

그림 5. 그림 4의 상황에서 두 번째와 세 번째 기계에 0.1씩을 더 할당한 경우.

같은 이치로 두 번째와 세 번째 기계에 작업을 할당시키다 보면 언젠가 총 부하가 다섯 번째 기계와 동일해지는 때가 옵니다.

그림 6. 두 번째와 세 번째 기계의 부하가 다섯 번째 기계의 부하와 동일해지는 시점.

현재까지 총 0.7의 작업을 할당해 주었으므로, 여전히 0.3이 남은 상태입니다. 이제부터는 자연스럽게 두 번째, 세 번째, 그리고 다섯 번째 기계에까지 작업을 동시에 할당해 주도록 하겠습니다. 그러면 아래 상태일 때 1의 작업을 모두 할당하게 됩니다.

그림 7. 작업을 모두 할당한 상태.

 

이렇게 작업을 할당해 준다면 우리가 원하는 대로 인접한 모든 기계에 동일한 부하를 줄 수 있게 됩니다. 물론 몇몇 기계에는 더 많은 부하가 실려있을 수 있습니다. 하지만 이는 이번 작업이 들어오기 전부터 이미 높은 부하를 가졌을 때뿐입니다. 그러한 기계에다가는 작업을 할당하지 않습니다.

 

고려하지 않은 경우가 하나 있습니다. 각 기계는 합해서 최대 1의 작업량을 할당 받을 수 있습니다. 따라서 작업을 넣는 작업을 진행하기 전에 인접한 기계들이 모두 부하가 높은 상황이라면, 작업을 인접한 기계에 모두 할당해 주지 못할 수 있습니다. 기존의 결정을 번복할 수 없으므로 인접한 기계가 모두 1의 부하를 받는 때가 오면, 남은 작업 조각들은 버리는 수밖에 없습니다.

 

이러한 방식으로 동작하는 알고리즘을 물 채우기 알고리즘(water-filling algorithm)이라고 부릅니다. 알고리즘이 동작하는 것을 보면 그러한 이름이 붙은 것이 직관적으로 다가올 것입니다. 새로운 작업이 도착했을 때, 각 인접한 기계들마다 할당받을 수 있는 여유분을 깊이로 하는 통에다가 용량이 1인 물을 붓는 것으로 생각할 수 있기 때문입니다. 들어간 물은 평평한 수면을 이룰 것이므로 종국적으로 인접한 기계들은 동일한 부하를 받게 될 것입니다. 만약 통의 깊이가 얕다면 모든 물을 부을 수 없을 것이고, 이때는 남은 물을 버려야 하겠습니다.

 

위 내용을 정형화하면 아래와 같이 적을 수 있습니다. 여기서 $(a{)}_{+}:=max\{a,0\}$을 의미합니다.

알고리즘 1. 물 채우기 알고리즘

---

초기 입력: 기계 $L$

출력: 할당 $\{x_e{\}}_{e\in E}$

 

1. 매 시각 작업 $j\in R$가 도착하면 아래를 수행한다.
   1. 인접한 기계 $i\in N(j)$에 대해, 현재까지 $i$가 할당 받은 작업량을 $d_i:=\sum _{e\in \delta (i)}{x}_e$라고 한다.
   2. $\sum _{i\in N(j)}(\ell (j)-d_i{)}_{+}=1$이 되도록 하는 $\ell (j)$을 찾는다.
   3. $\overline{\ell }(j)\leftarrow min\{\ell (j),1\}$.
   4. 인접한 기계 $i\in N(j)$에 대해, $x_{(i,j)}\leftarrow (\overline{\ell }(j)-d_i{)}_{+}$.

알고리즘 분석

이제 알고리즘을 분석해 보도록 하겠습니다. 아래의 논의는 이전 글을 참고하시면 이해하기 쉽습니다.

온라인 이분 매칭 랭킹 알고리즘 (Ranking Algorithm for Online Bipartite Matching)

 

앞에서 우리는 알고리즘의 출력 $x$가 결국은 아래 LP의 가능한 해(feasible solution)라고 했습니다.

$$\begin{array}{}\text{(P)}& \begin{array}{rl}\text{maximize }& {\displaystyle \sum _{e\in E}{x}_e}\\ \text{subject to }& {\displaystyle \sum _{e\in \delta (i)}{x}_e\le 1,}& \mathrm{\forall }i\in L,\\ & {\displaystyle \sum _{e\in \delta (j)}{x}_e\le 1,}& \mathrm{\forall }j\in R,\\ & x_e\ge 0,& \mathrm{\forall }e\in E.\end{array}\end{array}$$

이 LP의 쌍대는 아래와 같습니다.

$$\begin{array}{}\text{(D)}& \begin{array}{rl}\text{minimize }& {\displaystyle \sum _{i\in L}{\alpha }_i+\sum _{j\in R}{\beta }_j}\\ \text{subject to }& {\alpha }_i+{\beta }_j\ge 1,& \mathrm{\forall }(i,j)\in E,\\ & {\alpha }_i,{\beta }_j\ge 0,& \mathrm{\forall }i\in L,\mathrm{\forall }j\in R.\end{array}\end{array}$$

두 LP는 다음의 유용한 성질을 갖습니다.

정리 1. LP 쌍대성

---

LP (P)에 가능한 임의의 해 $x^{\ast }$와 LP (D)에 가능한 임의의 해 $(\alpha ,\beta )$에 대해, 항상 $$\sum _{e\in E}{x}_e^{\ast }\le \sum _{i\in L}{\alpha }_i+\sum _{j\in R}{\beta }_j$$를 만족한다.

따라서 만약 우리가 $$\sum _{e\in E}{x}_e\ge \gamma (\sum _{i\in L}{\alpha }_i+\sum _{j\in R}{\beta }_j)$$를 만족하는 LP (D)에 가능한 해 $(\alpha ,\beta )$를 찾는다면, 이 알고리즘이 $\gamma$-경쟁 알고리즘이 된다는 것을 보일 수 있게 됩니다.

 

그러한 $(\alpha ,\beta )$를 만드는 방법을 바로 설명할 수도 있겠지만, 그러면 직관적으로 이해하기 어렵다고 생각합니다. 저 또한 원래 증명을 머리로는 알고 있었습니다만, 마음으로는 받아들이지 못하는 상황이었습니다. 최근 관련 주제로 연구를 하면서 다시 공부할 일이 있었는데, 이번에 증명을 나름 직관적으로 이해하는 좋은 방법을 찾았습니다. 이 글을 작성하게 된 계기도 이 증명을 기록하고 싶었기 때문입니다.

 

쌍대 문제 (D)에 가능한 해는 직관적으로 무엇에 해당할까요? 한번 $(\alpha ,\beta )$의 모든 값이 0 또는 1만을 갖는다고 가정해 봅시다. 정점들 중에서 ${\alpha }_i=1$인 $i$와 ${\beta }_j=1$인 $j$를 모아서 $S$라고 부르겠습니다. LP (D)의 제약 조건에 의해서 우리는 각 간선 $(i,j)\in E$에 대해 ${\alpha }_i=1$이거나 ${\beta }_j=1$이라는 사실을 알 수 있습니다. 다시 말해 $i$와 $j$ 중 적어도 하나는 $S$에 속해야 한다는 뜻입니다. 이러한 조건을 만족하는 $S$를 우리는 특별한 이름으로 부릅니다. 바로 정점 덮개(vertex cover)입니다. 즉 LP (D)는 정점 덮개의 선형 계획법 완화에 해당합니다.

 

이분 매칭의 쌍대 문제가 정점 덮개를 표현한다는 사실은 그다지 놀라운 일이 아닙니다. 둘 사이의 연관성은 다음의 유명한 정리에서 확연히 드러납니다.

정리 2. 쾨니그의 정리

---

어떤 이분 그래프가 주어졌을 때, 이분 그래프의 최대 매칭의 크기는 최소 정점 덮개의 크기와 동일하다.

위 정리가 궁금하신 분들은 아래의 글을 참고하시기 바랍니다.

쾨니그의 정리 (Kőnig's Theorem)

쾨니그의 정리를 통해 우리는 이분 그래프 $G=(L\cup R,E)$의  최소 정점 덮개 $S$가 다음 성질들을 만족한다는 것을 알 수 있습니다.

• $L$과 $R$은 각각 $L\cap S$, $L\setminus S$와 $R\cap S$와 $R\setminus S$로 분할(partition)된다.
• $L\setminus S$와 $R\setminus S$에는 간선이 존재하지 않는다.
• $L\cap S$의 모든 정점이 $R\setminus S$의 정점과 짝지어지는 매칭이 존재한다.
• $R\cap S$의 모든 정점이 $L\setminus S$의 정점과 짝지어지는 매칭이 존재한다.

그림 8. 쾨니그의 정리에 의해 보장된 정점 집합 $S$의 예시.

 

각 조건을 만족하는 이유를 논의해 보겠습니다. 먼저, 만약 $L\setminus S$와 $R\setminus S$에 간선이 존재한다면, $S$는 정점 덮개조차 아니게 되므로 두 번째 조건은 성립해야 합니다. 세 번째와 네 번째 조건은 최대 매칭의 크기와 동일해야 하므로 만족합니다. 예를 들어 어떤 매칭이 $L\cap S$의 한 정점과 $R\cap S$의 한 정점을 짝지어 준다고 해 봅시다. 그러면 그 매칭의 크기는 죽었다 깨어나도 $|S|$가 될 수 없습니다. 따라서, 크기가 반드시 $|S|$여야 하는 최대 매칭에서는 $L\cap S$의 정점들은 $R\setminus S$의 정점들과, $R\cap S$의 정점들은 $L\setminus S$의 정점들과만 짝지어져야 합니다. 그 크기가 정확히 $|S|$이려면 $L\cap S$와 $R\cap S$의 모든 정점들이 짝지어져야 합니다.

 

각설하고, 우리의 목표가 무엇이었는지 다시 생각해 보겠습니다. 우리의 목표는 알고리즘의 출력 $x$에 대해, $$\begin{array}{}\text{(1)}& \sum _{e\in E}{x}_e\ge \gamma (\sum _{i\in L}{\alpha }_i+\sum _{j\in R}{\beta }_j)\end{array}$$를 만족하는 LP (D)에 가능한 해 $(\alpha ,\beta )$를 찾는 것입니다. 그러기 위해서는 가능한 $\sum _{i\in L}{\alpha }_i+\sum _{j\in R}{\beta }_j$의 값이 작아야 하겠습니다. 만약 최종 입력 그래프에 대한 최소 정점 덮개 $S$를 안다면, $${\alpha }_i:=\{\begin{array}{ll}1,& i\in L\cap S\\ 0,& i\in L\setminus S,\end{array}{\beta }_j:=\{\begin{array}{ll}1,& j\in R\cap S,\\ 0,& j\in R\setminus S\end{array}$$를 해 주는 것으로 좋은 쌍대 해를 얻을 수 있습니다.(사실은 최적해입니다.)

 

문제는 알고리즘이 동작하는 도중에는 전체 입력이 어떻게 될지 모르므로 $S$를 알 수 없다는 데에 있습니다. 대신 각 기계 혹은 작업의 상태에 따라 어렴풋이 유추해 볼 수는 있겠습니다. 먼저 기계의 입장에서 생각해 보겠습니다. 알고리즘이 거의 끝나는 와중에 해당 기계에 할당된 부하가 크다면 아무래도 $S$에 속할 것으로 예측할 수 있습니다. 최대 매칭에서 $L\cap S$의 모든 정점은 짝지어져야 하기 때문이죠. 반대로 부하가 작은 기계는 $S$에 속할 가능성이 낮을 것입니다.

 

이번에는 작업의 경우를 생각해 봅시다. 어떤 작업을 처리한 후에 인접한 작업들의 부하가 작다면, 이 작업은 $S$에 속할 공산이 큽니다. 앞에서 인접한 기계들의 부하가 작다면 $L\setminus S$에 들어갈 가능성이 높다고 했는데, 해당 기계들은 $R\cap S$의 작업에만 인접할 수 있기 때문입니다. 반대로 인접한 기계들의 부하가 크다면, 해당 기계들이 $L\cap S$에 속할 가능성이 높으므로 이 작업은 $S$에 속하지 않을 것을 예상할 수 있겠습니다.

 

정리하자면 다음과 같습니다.

• 각 기계 $i\in L$는 그것에 할당된 부하가 클수록 $S$에 들어갈 것이다.
• 각 작업 $j\in R$는 이 작업을 처리한 후 인접한 기계들의 부하가 크지 않다면 $S$에 들어갈 것이다. 

기계에 할당된 부하는 $d_i:=\sum _{e\in \delta (i)}{x}_e$와 같습니다. 따라서 $S$에 $i$가 들어갈지 여부는 $d_i$로 결정해도 괜찮을 것입니다. 그렇다면 각 작업 $j$가 $S$에 들어가는지 여부를 나타내는 적절한 척도는 무엇일까요? 바로 $\overline{\ell }(j)$입니다. 이 값은 작업 $j$를 처리한 후 인접한 기계 중 $j$의 작업이 조금이라도 할당된 기계들의 부하 값이므로, $\overline{\ell }(j)$의 값이 작을 때 $S$에 $j$가 들어간다고 해석하는 것이 직관적으로 그리 무리는 아닐 것입니다.

 

$f(0)=0$, $f(1)=1$을 만족하는 미분 가능한 증가 함수 $f$를 하나 생각해 보겠습니다. 그리고 각 기계 $i\in L$에 대해서는 매번 ${\alpha }_i\leftarrow f(d_i)$를 갖도록 하고, 각 작업 $j\in R$에 대해서는 ${\beta }_j\leftarrow 1-f(\overline{\ell }(j))$의 값을 갖도록 해 보겠습니다. 참고로 ${\alpha }_i$는 알고리즘이 진행됨에 따라 변화할 수 있으나, ${\beta }_j$는 작업 $j$가 처리된 후에는 고정된 값을 갖습니다. 이러면 $(\alpha ,\beta )$가 앞에서 논의한 사항을 잘 반영한다는 것을 확인할 수 있습니다.

 

이렇게 정의된 $(\alpha ,\beta )$는 우리가 원하는 목표의 절반을 이루어 줍니다.

정리 3. 가능한 쌍대 해

---

$(\alpha ,\beta )$는 쌍대 문제 (D)에 가능한 해이다.

[증명] $\alpha ,\beta \ge 0$은 자명합니다. 각 간선 $(i,j)\in E$에 대해, $j$가 처리된 후 기계 $i$의 부하는 적어도 $\overline{\ell }(j)$이고, 이후 줄지 않습니다. 따라서 $d_i\ge \overline{\ell }(j)$를 만족하고, $${\alpha }_i+{\beta }_j=f(d_i)+1-f(\overline{\ell }(j))\ge f(\overline{\ell }(j))+1-f(\overline{\ell }(j))=1$$이 성립합니다. ■

 

남은 것은 식 (1)을 만족하는 적절한 $\gamma$를 찾는 것입니다.

정리 4. 알고리즘의 경쟁성

---

알고리즘의 출력 $x$와 함수 $f$에 의해 만들어진 쌍대 해 $(\alpha ,\beta )$는 $$\gamma =\frac{1}{\underset{t\in [0,1]}{max}\{1-f(t)+f^{\prime }(t)\}}$$에 대해 식 (1)을 만족한다.

[증명] 편의를 위해 $$P:=\sum _{e\in E}{x}_e,D:=\sum _{i\in L}{\alpha }_i+\sum _{j\in R}{\beta }_j,\mathrm{\Gamma }:=\underset{t\in [0,1]}{max}\{1-f(t)+f^{\prime }(t)\}$$라고 쓰겠습니다. 이제 알고리즘이 시작할 때를 고려해 봅시다. 아직까지 할당한 것이 하나도 없으므로 $P=0$입니다. 또한, $f(0)=0$이라고 하였으므로, $Q=0$을 만족합니다. 따라서 만약 매 작업 $j$에 대해, 이 작업을 처리한 후 $P$와 $D$의 변화량 $\mathit{\Delta }P$와 $\mathit{\Delta }Q$가 $$\mathrm{\Gamma }\mathit{\Delta }P\ge \mathit{\Delta }Q$$를 만족함을 보인다면 증명이 완성됩니다.

 

각 $i\in N(j)$에 대해, $d_i$는 이번 작업을 처리하기 직전 각 $i$가 그동안 받은 할당량이라고 하겠습니다. 이제 임의의 $t\in [0,1]$에 대해, $n(t)$를 $t$보다 적은 양을 할당 받은 기계의 대수라고 하겠습니다. 즉, $$n(t):=|\{i\in N(j)\mid d_i\le t\}|$$입니다. 이전 절에서 활용한 예시에 대해 도식적으로 나타내면 아래와 같습니다.

그림 9. $n(t)$의 예시.

직관적으로 설명하면, $t$는 일종의 "수심(水深)"에 해당하고, $n(t)$는 수심이 $t$보다 "낮은" 기계들의 대수를 의미합니다.

 

이 정의를 활용하면 $\mathit{\Delta }P$와 $\mathit{\Delta }Q$를 각각 수심 $t$에 대한 식으로 표현할 수 있습니다. 먼저, $$\mathit{\Delta }P=\sum _{e\in \delta (j)}{x}_e={\int }_0^{\overline{\ell }(j)}n(t)dt$$가 성립함을 확인하시기 바랍니다. 알고리즘의 동작을 수심이 $t$가 되었을 때 $d_i\le t$인 기계 $i\in N(j)$에 동일한 속도로 작업을 할당하는 것으로 볼 수 있기 때문입니다.

 

이제 $\mathit{\Delta }Q$를 생각해 보겠습니다. 이는 $\alpha$가 증가한 양과 $\beta$가 증가한 양으로 나눌 수 있습니다. 각 기계 $i\in N(j)$의 부하는 $d_i$에서 $max\{\overline{\ell }(j),d_i\}$로 바뀌었습니다. 따라서, $$\mathit{\Delta }{\alpha }_i=f(max\{\overline{\ell }(j),d_i\})-f(d_i)={\int }_{d_i}^{max\{\overline{\ell }(j),d_i\}}{f}^{\prime }(t)dt$$로 쓸 수 있습니다. 이를 모두 더하면, $$\sum _{i\in N(j)}\mathit{\Delta }{\alpha }_i={\int }_0^{\overline{\ell }(j)}{f}^{\prime }(t)n(t)dt$$와 동일합니다.

 

마지막으로 $\beta$의 증가량은 ${\beta }_j$의 값이 $1-f(\overline{\ell }(j))$로 바뀌는 것과 같습니다. 만약 $\overline{\ell }(j)=1$이라면 $f$가 $f(1)=1$을 만족하는 증가함수라는 조건에 의해 $${\beta }_j=0\le {\int }_0^{\overline{\ell }(j)}(1-f(t))n(t)dt$$임을 알 수 있습니다. 반면, $\overline{\ell }(j)=\ell (j)$라면, 작업 $j$는 1의 작업량을 모두 할당했다는 의미이므로 ${\int }_0^{\ell (j)}n(t)dt=1$이 되며, 따라서 $$1-f(\ell (j))=(1-f(\ell (j))){\int }_0^{\ell (j)}n(t)dt\le {\int }_0^{\ell (j)}(1-f(t))n(t)dt$$를 유도할 수 있습니다.

 

이를 모두 조합하면, $$\mathit{\Delta }Q\le {\int }_0^{\overline{\ell }(j)}(f^{\prime }(t)+1-f(t))n(t)dt\le \mathrm{\Gamma }{\int }_0^{\overline{\ell }(j)}n(t)dt=\mathrm{\Gamma }\mathit{\Delta }P$$를 이끌어 낼 수 있습니다. ■

 

이제 남은 것은 적절한 $f$를 결정하는 일입니다. 찾고 싶은 $f$의 조건을 다시 적어 보자면 아래와 같습니다.

• $f$는 미분 가능한 증가함수이다.
• $f(0)=0$, $f(1)=1$을 만족한다.
• $\mathrm{\Gamma }=\underset{t\in [0,1]}{max}\{1-f(t)+f^{\prime }(t)\}$를 최소화한다.

$f(t):=\frac{e^t-1}{e-1}$로 정의하면 위 조건을 모두 만족하면서 $\mathrm{\Gamma }=\frac{e}{e-1}$이 됨을 보일 수 있습니다. 따라서 알고리즘의 경쟁비는 $\gamma =1/\mathrm{\Gamma }=1-1/e$가 됩니다.

마치며

이것으로 온라인 분수 이분 매칭 문제에 대한 설명을 마칩니다. 특히, 본문에서는 이 문제를 $1-1/e$의 경쟁비로 해결하는 결정론적 알고리즘인 물 채우기 알고리즘에 대해 깊이 다루었습니다. 이제 궁금한 점은 분명 더 좋은 경쟁비를 가질 수 있는지입니다. 정수 문제에서 처럼 랜덤 알고리즘을 사용하면 혹여나 더 좋은 경쟁비를 가질 수도 있겠습니다. 하지만 안타깝게도, 이 문제는 더 이상, 심지어 랜덤 알고리즘이라 할지라도 더 좋은 경쟁비로 해결할 수 없습니다. 다음 시간에는 이에 대해 알아 보도록 하겠습니다.

 

고맙습니다. :)

참고자료

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