온라인 가중치 이분 매칭 (Online Weighted Bipartite Matching)

Photo by Piret Ilver on Unsplash

저번 글에서는 온라인 이분 매칭 문제(online bipartite matching problem)가 무엇인지 설명하고 이를 경쟁적으로 해결하는 알고리즘에 대해서 알아 보았습니다. 문제를 간략히 다시 소개하도록 하겠습니다.

처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 태운 적이 없는 택시 가운데 하나를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 매번 바로 결정해야 한다. 이 결정은 차후에 번복될 수 없다. 이때, 최대한 많은 승객을 태우시오.

위 예시에서 한 가지 현실과는 약간 동떨어진 점이 있다면 바로 건당 정액을 받는 수익 구조라는 것입니다. 이 때문에 최대한 많은 승객을 태우는 것이 문제의 목표가 되었지요. 하지만 실상은 다릅니다. 각 택시의 현재 위치나 승객의 목적지 등에 의해서 발생하는 비용이나 벌 수 있는 수익이 달라지게 됩니다. 따라서 가능한 택시-승객 쌍에 대해 비용이나 수익에 해당하는 일종의 가중치(weight)를 두고 이를 최소화하거나 최대화하는 할당 방법을 찾는 것이 훨씬 현실적인 시나리오입니다.

 

이번 시간에는 온라인 이분 매칭 문제에 간선마다 가중치가 있어 최소 혹은 최대의 가중치를 갖는 매칭을 찾는 문제를 여러 각도에서 공부해 보겠습니다. 본문의 내용을 간략히 요약하면 다음과 같습니다.

• 최대 가중치 매칭(maximum-weight matching)을 찾는 문제를 해결하는 어떤 알고리즘도 (심지어 랜덤 알고리즘이라고 할지라도) \( \frac{2}{n+1} \)보다 좋은 경쟁비를 가질 수 없다.
• 최소 가중치 매칭(minimum-weight matching)을 구하는 문제는 일반적으로 완전 이분 그래프(complete bipartite graph) 위에서 모든 정점이 참여하는 최소 가중치 완전 매칭(minimum-weight perfect matching)을 찾는 것을 의미하며, 이 문제는 유한의 경쟁비로는 해결할 수 없다.
• 최대 가중치 매칭을 찾는 문제에서 만약 택시 정점이 기존에 할당된 승객 정점보다 현재 새로 들어온 승객 정점으로부터 얻는 이득이 커서 기존 승객을 아무런 손해 없이 버리고 새 승객을 받을 수 있다면, \(\frac{1}{2}\)의 경쟁비를 갖는 알고리즘이 존재한다. 이 문제를 자유 처분이 있는 온라인 최대 가중치 매칭(online maximum-weight matching with free disposal)이라고 한다.

아래 내용은 온라인 알고리즘(online algorithm) 및 경쟁성 분석(competitive analysis)을 잘 알고 있다는 전제로 작성되었습니다. 이에 익숙하지 않으신 분들은 제 이전 포스트를 참조하시기 바랍니다.

2020/03/14 - [온라인 알고리즘/Basic] - 온라인 알고리즘 (Online Algorithm)

온라인 알고리즘 (Online Algorithm)

또한 많은 내용이 아래 글의 연장선에서 작성되었으므로 참고하시기 바랍니다.

2020/11/07 - [온라인 알고리즘/Online matching] - 온라인 이분 매칭 (Online Bipartite Matching)

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

문제 정의

입력으로는 어떤 이분 그래프(bipartite graph) \(G = (L \cup R, E) \)와 함께 음이 아닌 가중치 \(w : E \to \mathbb{R}_+\)가 주어집니다. 여기서 음이 아닌 가중치만 고려하는 이유는 그렇지 않으면 경쟁비(competitive ratio)의 정의가 모호해지기 때문입니다.

 

이전 포스트에서와 같이 \(L\)은 가용할 수 있는 택시에 대응하고, \(R\)은 승객에 대응한다고 하겠습니다. 우리는 처음에 \(L\)에 대한 정보는 가지고 있지만 \(R\)에 대한 정보는 하나도 모릅니다. 대신 시간이 흐르면서 승객 정점 \(j\)가 하나씩 밝혀지게 되고 동시에 그제야 \(j\)에 인접한(adjacent) 택시 \(i\)와 가중치 \( w(i, j) \)의 정보를 알게 됩니다. 우리는 승객 \(j\)를 택시에 할당할지를 결정해야 하며, 만약 할당한다면 어떤 택시에 할당할지를 결정해야 합니다. 이 결정은 미래에 번복될 수 없습니다.

 

승객은 최대 한 택시에만 탈 수 있고, 택시도 최대 한 승객만 태울 수 있다고 합시다. 그러면 우리가 찾는 것은 \(G\) 위의 매칭(matching)에 해당하게 되지요. 매칭 \(M\)의 가중치를 \(M\)에 속한 간선의 가중치를 모두 합한 것으로 정의하겠습니다. 이를 기호로 \( w(M) := \sum_{e \in M} w(e)\)로 표현하겠습니다. 우리의 목표는 \( w(M) \)이 최대 혹은 최소가 되는 매칭 \(M\)을 찾는 것입니다.

최대 가중치 매칭

먼저 최대 가중치 매칭을 찾는 문제를 생각해 보겠습니다. 안타깝게도 우리는 어떤 알고리즘도 0보다 큰 어떤 상수의 경쟁비를 가질 수 없다는 것을 보일 수 있습니다.

정리 1. 임의의 가중치를 가질 때 최대 가중치 매칭 문제의 경쟁비

---

임의의 가중치를 가질 때 최대 가중치 매창을 구하는 알고리즘은 (심지어 랜덤 알고리즘이라도) \( \frac{2}{n+1}\)보다 좋은 경쟁비를 가질 수 없다. 여기서 \(n\)은 들어온 승객의 수이며 따라서 승객이 많아질수록 알고리즘의 성능은 나빠진다.

[증명] 최대로 들어오는 승객의 수 \(n\)에 대해서 총 \(n\) 개의 무지각형 상대방(oblivious adversary)을 고려하겠습니다. 이때, \(k\) 번째 상대방이 가지는 그래프 \(G_k := (L_k \cup R_k, E_k)\)는 다음과 같이 정의됩니다.

• \(L_k := \{i\} \), \(R_k := \{ j_1, j_2, \cdots, j_k \}\)
• \(E_k := \{ (i, j_1), (i, j_2), \cdots, (i, j_k) \} \)
• 임의의 \((i, j_\ell) \in E_k\)에 대해 \( w(i, j_\ell) = 2^{\ell-1} \)

그림 1. 정리 1의 \(k\) 번째 상대방이 \(G_k\)를 보여주는 방법.

다시 말해, 택시는 한 대만 있고 승객은 계속 들어오는데 새로운 승객이 들어올 때마다 마지막 가중치의 두 배의 가중치를 갖는 입력입니다. 따라서 마지막으로 들어오는 승객을 택시에 할당해 주어야 최대 매칭을 구하게 되는데, 문제는 마지막 승객이 언제 들어올지 알고리즘으로서는 알 방법이 없다는 것입니다. 알고리즘은 임의의 상대방에 대해 모두 경쟁적으로 동작해야 하므로 첫 번째 승객이 들어왔을 때, 지금 상대하는 상대방이 첫 번째 상대방이어서 이번에 골라야 할지아니면 두 번째 상대방이어서 할당하지 않고 버티는 게 이득일지 알 수 없습니다. 이를 통해 알고리즘의 경쟁성을 망칠 수 있게 되죠.

 

직관적으로 알아 봤으니 엄밀히도 증명해 봅시다. 어떤 (랜덤) 알고리즘이 \(\ell\) 번째 승객 \(j_\ell\)이 들어왔을 때 택시 \(i\)에 할당할 확률을 \(p_\ell\)이라고 합시다. 앞에서 살펴본 대로 알고리즘은 현재 자신이 어떤 상대방을 상대하는지 모르기 때문에 어떤 상대방에 대해서도 동일한 \(p_\ell\)을 가질 것입니다.

 

먼저 첫 번째 상대방을 상대한다고 합시다. 이 상대방은 첫 번째 승객을 택시에 할당해 줄 것이므로 1의 최적값을 갖습니다. 알고리즘은 \(p_1\)의 확률로 \(j_1\)을 \(i\)에 할당했을 것이고, 따라서 알고리즘이 \(\rho\)의 경쟁비를 갖기 위해서는 \[ p_1 \geq \rho \]를 만족해야 합니다.^[ㄱ] 하나 더 보도록 합시다. 두 번째 상대방에 대해서, 이 상대방은 두 번째 승객을 택시에 할당해 줄 것이므로 2의 최적값을 갖습니다. 알고리즘은 \(p_1\)의 확률로 \(j_1\)을, \(p_2\)의 확률로 \(j_2\)를 \(i\)에 할당할 겁니다. 따라서, \[ p_1 + 2 p_2 \geq 2 \rho \]를 만족해야 합니다.

 

이를 확장하여, \(k\) 번째 상대방을 상대할 때 알고리즘이 \(\rho\)의 경쟁비를 갖기 위해서는 \[ \sum_{\ell = 1}^k 2^{\ell-1}p_\ell \geq 2^{k-1} \rho \]를 만족해야 한다는 것을 유추할 수 있습니다. 이 부등식에 어떤 음이 아닌 수 \(s_k \geq 0\)을 도입하여 다음과 같이 등식으로 바꾸어 주도록 하겠습니다. \[ \sum_{\ell = 1}^k 2^{\ell-1}p_\ell = 2^{k - 1} \rho + s_k \tag{1} \] \(k \geq 2\)일 때, 이 등식의 좌변을 아래와 같이 약간 수정해 보겠습니다. \[ \sum_{\ell = 1}^k 2^{\ell-1}p_\ell = 2^{k-1}p_k + \sum_{\ell=1}^{k - 1} 2^{\ell - 1} p_\ell = 2^{k - 1}p_k +2^{k-2} \rho + s_{k-1} \] 여기서 마지막 등식은 \(k - 1\) 번째 상대방을 상대할 때의 식 1에서 얻을 수 있습니다. 이렇게 얻은 식을 식 1의 좌변에 다시 대입하면 \[ p_k = \frac{\rho}{2} + \frac{s_k - s_{k - 1}}{2^{k-1}} \tag{2} \]을 이끌어낼 수 있습니다.

 

알고리즘이 어떤 승객을 택시에 할당하는 사건은 상호 배타적(mutually disjoint)입니다. 예를 들어, 첫 번째 승객을 택시에 할당했을 때 다른 나머지 승객은 택시에 할당될 수 없습니다. 따라서 전체 확률의 법칙(law of total probability)에 의해, \[ p_1 + p_2 + \cdots +p_n \leq 1 \]임을 알 수 있습니다. 여기서 좌변에 앞에서 구한 식 1(\(k = 1\)), 2(\(k \geq 2\))를 대입하면 \[ \rho + s_1 + \sum_{k = 2}^n \left[ \frac{\rho}{2} + \frac{s_k - s_{k - 1}}{2^{k-1}} \right] = \frac{n+1}{2} \cdot \rho + \sum_{k = 1}^{n-1} \frac{s_k}{2^k} + \frac{s_n}{2^{n - 1}} \leq 1 \]을 얻을 수 있습니다. 앞에서 우리는 \(s_1, \cdots, s_n\)이 모두 음이 아닌 수라고 하였으므로 위 부등식에서 \[ \rho \leq \frac{2}{n+1} \]을 이끌어낼 수 있죠. 이는 어떤 알고리즘을 갖고 오더라도 앞에서 말씀드린 \(n\) 개의 상대방을 모두 상대하려면 아무리 좋아도 \( \frac{2}{n+1} \)의 경쟁비를 가질 수 밖에 없다는 의미이며, 이로써 정리의 증명이 완성됩니다. ■

최소 가중치 완전 매칭

가중치가 최소인 매칭을 찾는 문제는 사정이 좀 복잡합니다. 앞에서 경쟁비의 정의 때문에 음이 아닌 가중치만 고려하는 것이 일반적이라고 말씀드렸습니다. 따라서 찾아야 하는 매칭에 아무런 제약이 없으면 아무것도 고르지 않는 알고리즘이 항상 최적해를 출력하는 자명한 상황에 빠집니다.

 

따라서 \(|L| = |R|\)인 완전 이분 그래프(complete bipartite graph)에서 최소의 가중치를 갖는 완전 매칭(perfect matching)을 찾는 문제를 고려하는 것이 일반적입니다. 모든 정보가 주어지는 오프라인(offline) 버전에서 이 문제는 할당 문제(assignment problem)라는 이름으로도 잘 알려져 있고, 헝가리안 알고리즘(Hungarian algorithm) 등 다항 시간에 최소 가중치 완전 매칭을 찾는 알고리즘이 존재합니다. 어쩌면 이 문제는 온라인 할당 문제(online assignment problem)라고 불러도 좋겠습니다.

 

이 문제는 최대 가중치의 매칭을 찾는 이전 문제보다 상황이 훨씬 열악합니다. 알고리즘으로 하여금 0보다 큰 가중치를 갖도록 만드는 상대방이 만약 0의 최적값을 갖는다면 경쟁비는 무한대가 되기 때문입니다.

정리 2. 임의의 가중치를 가질 때 최소 가중치 완전 매칭 문제의 경쟁비

---

\(|L| = |R|\)인 완전 이분 그래프 상에서 임의의 가중치를 가질 때 최소 가중치 완전 매칭을 구하는 알고리즘은 (랜덤 알고리즘이라도) 유한의 경쟁비를 가질 수 없다.

[증명] 이번에는 알고리즘이 다음 두 상대방을 상대하게 만들어 봅시다. 두 상대방 모두 \(L = \{i_1, i_2\}\)를 알고리즘에게 먼저 알려 줍니다. 또 두 상대방 모두 첫 번째 승객 \(j_1\)에 대해 \(w(i_1, j_1) = w(i_2, j_2) = 0\)의 가중치를 갖는 간선을 보여 줍니다. 그러면 알고리즘은 둘을 분간할 수 없으므로 \(p\)의 확률로 \(j_1\)을 \(i_1\)에 할당하고 반대로 \(1-p\)의 확률로는 \(i_2\)에 할당할 것입니다.

 

두 번째 승객 \(j_2\)가 들어오는 이때에 두 상대방의 동작이 달라집니다. 첫 번째 상대방은 \( w(i_1, j_2) = 1 \), \( w(i_2, j_2) = 0 \)을 보여주고, 두 번째 상대방은 \( w(i_1, j_2) = 0 \), \( w(i_2, j_2) = 1 \)을 보여 줍니다. 그러면 두 상대방 모두 0의 가중치를 갖는 완전 매칭이 존재합니다. 하지만 알고리즘은 첫 번째 상대방을 상대로는 \(1-p\)의 확률로 이미 \( i_2\)를 \(j_1\)에 할당해 주었으므로 울며 겨자 먹기로 \( 1-p \)의 확률로 \( j_2 \)를 \(i_1\)에 할당해 주어야 합니다. 그럼에도 유한의 경쟁비 \(\rho\)를 갖기 위해서는 \[ 1-p \leq \rho \cdot 0 = 0 \]을 만족해야 하죠.^[ㄴ] 따라서 가능한 상황은 \(p=1\) 밖에 없습니다. 문제는 그렇게 되면 두 번째 상대방을 상대로는 반드시 \( j_2 \)를 \(i_2\)에 할당할 수 밖에 없게 되고, 따라서 이 상대방을 상대로는 유한의 경쟁비를 얻을 수 없게 됩니다. ■

그림 2. 정리 2의 두 상대방이 각자의 그래프를 알고리즘에 보여주는 방식.

기존 승객을 손해 없이 버릴 수 있을 때

앞에서 우리는 최대 가중치 매칭 문제나 최소 가중치 완전 매칭 문제는 풀기 어려운 문제라는 것을 보였습니다. 그 때문에 학계에서는 이와 관련된 다양한 변종(variant) 문제들을 찾아 보고, 그 문제들에서는 좋은 경쟁 알고리즘을 얻을 수 있는지를 연구하였죠. 이번 절에서는 그중에서도 가장 잘 알려진 변종을 하나 소개해 드리겠습니다.

 

최대 가중치 매칭 문제가 경쟁적으로 풀기 어려운 이유는 결정을 번복할 수 없기 때문이었습니다. 언젠가 들어온 승객을 한번 어떤 택시에 할당해 주면 나중에 더 좋은 가중치를 갖는 승객이 와도 이를 처리해 줄 수 없었죠. 만약 이러한 경우에 기존 승객을 아무런 손해 없이 버리고 좋은 가중치를 제공하는 승객을 대신 받는다면 어떻게 될까요? 이 문제가 바로 최대 가중치 매칭 문제에서 가장 일반적으로 연구되는 변종인 자유 처분이 있는 최대 가중치 매칭 문제(maximum weight matching problem with free disposal)입니다.

 

흥미롭게도 우리는 이 문제를 \(\frac{1}{2}\)의 경쟁비로 해결하는 결정론적 알고리즘(deterministic algorithm)을 만들 수 있습니다. 아래에서 \(n := |R|\)은 (알고리즘은 모르는) 승객의 수를 나타냅니다.

알고리즘 1. 자유 처분이 있는 최대 가중치 매칭 문제의 0.5-경쟁 알고리즘

---

초기 입력: 택시 정점의 집합 \(L\)

출력: 매칭

 

1. \(M_0 \gets \emptyset \)
2. \(k\) 번째 승객 \(j_k \in R\)가 들어올 때마다 다음을 수행한다.
   1. 각 택시 \(i \in L\)에 대해, \(v^k_i\)를 만약 \(i\)가 \(M_{k-1}\)에 참여하고 있으면 \(i\)가 \(M_{k-1}\)에서 인접한 간선의 가중치로, 만약 참여하고 있지 않으면 0으로 정의한다.
   2. 각 택시 \(i \in L\)에 대해, \( w(i, j_k) - v^k_i \)를 구한다. 그중에서 가장 큰 값이 0보다 크지 않으면 \(j_k\)는 할당시키지 않고 끝낸다.
   3. 0보다 큰 경우에는 가장 큰 값을 이루는 택시 중 아무것 하나를 \(i^*\)라고 부른다. 만약 \(i^*\)가 \(M_{k - 1}\)에 참여하고 있으면 해당 간선을 버리고 \((i^*, j_k)\)를 대신 넣는다. 그렇지 않으면 그냥 \( (i^*, j_k) \)를 매칭에 넣는다.
   4. 단계 2와 3을 거친 후에 얻은 매칭을 \(M_k\)라고 한다.
3. 마지막으로 얻은 \(M_n\)를 반환한다.

알고리즘이 동작하는 방식은 결국 매번 승객이 들어왔을 때 그 승객을 각 택시에 (경우에 따라서는 기존에 할당된 승객을 버리면서라도) 할당해 주었을 때 얻는 추가적인 이득(marginal gain)이 가장 큰 택시에 승객을 할당해 주는 것입니다. 만약 0보다 작아서 손해가 나는 상황이라면 그냥 버리고 말이죠.

 

이제 이 알고리즘이 의도한 경쟁비를 갖는다는 것을 보이도록 하겠습니다. 그러기 위해서 먼저 몇 가지를 정의해야 합니다. 먼저 매 \(k\) 번째 승객이 들어온 것을 처리했을 때 알고리즘이 얻는 이득을 \(p_k\)라고 하겠습니다. 다시 말해, \[ p_k := w(M_k) - w(M_{k - 1}) \]로 정의하겠습니다. 다음 문제의 최적해 하나를 \(M^*\)로 고정하겠습니다. 그러면 다음과 같이 매번 얻는 이득이 그렇게 작지 않음을 보일 수 있습니다.

정리 3. 매번 추가적인 이득의 크기

---

모든 \(k = 1, \cdots, n\)에 대해, 만약 \(j_k\)가 \(M^*\)에서 \(i_k\)에 할당이 되었다고 하자. 그러면 \[ p_k \geq w(i_k, j_k) - v^k_{i_k} \]를 만족한다.

[증명] 알고리즘이 단계 2-b와 2-c에서 동작하는 것을 살펴 보면 쉽게 알 수 있습니다. 매번 각 \(i \in L\)에 대해 우변의 값을 계산한 것 중에 가장 큰 것을 취하기 때문입니다. ■

 

다음은 \(i\)가 \(M_{k-1}\)에 의해 할당된 간선의 가중치에 해당하는 \(v^k_i\)의 값이 \(k\)가 커질 때마다 값이 작아지지 않는다는 것을 보이겠습니다. 여기서 \(v^{n+1}_i\)는 최종 결과 \(M_n\)에 대해 단계 2-a를 가상으로 수행했을 떄 얻는 값을 의미합니다.

정리 4. 할당된 간선 가중치의 증가성

---

임의의 \(i \in L\)에 대해, \[  v^1_i \leq v^2_i \leq \cdots \leq v^{n+1}_i \]를 만족한다.

[증명] 이것 또한 알고리즘이 어떻게 동작하는지를 잘 따지면 쉽게 관찰할 수 있습니다. 만약 \(i\)가 알고리즘의 단계 2-c에 의해 새로이 할당되지 않았다면 다음 단계에서도 동일한 값을 가질 것입니다. 따라서 \(i\)가 단계 2-c에 의해 새로 들어온 승객 \(j_k\)에 할당된 경우가 문제인데, 사실 단계 2-c가 수행될 조건은 \( w(i, j_k) - v^k_i > 0 \)이기 때문에 \[ v^k_i < w(i, j_k) = v^{k+1}_i \]가 됩니다. ■

 

앞에서 보인 두 정리를 조합하면 원하는 결과를 얻을 수 있습니다.

정리 5. 알고리즘 1의 경쟁성

---

알고리즘 1은 \(\frac{1}{2}\)의 경쟁비를 갖는다.

[증명] 정리 3의 부등식을 모든 \(k = 1, \cdots, n\)에 대해서 더하면 다음을 얻습니다. \[ \sum_{k = 1}^n p_k \geq \sum_{k = 1}^n w(i_k, j_k) - \sum_{k = 1}^n v^k_{i_k} \] 먼저 \(p_k\)의 정의에 의해, \[ \sum_{k = 1}^n p_k = w(M_n) \]이 됩니다. 또한 \[ \sum_{k = 1}^n w(i_k, j_k) = w(M^*) \]임도 쉽게 알 수 있습니다. 약간 복잡한 부분은 마지막 항인데, 이는 정리 4를 통해 분석할 수 있습니다. \(v^k_i\)가 \(k\)가 커지면 작아지지 않는다는 성질을 통해, \[ \sum_{k = 1}^n  v^k_{i_k} \leq \sum_{k = 1}^n v^{n + 1}_{i_k} \leq w(M_n)\]임을 알 수 있습니다. 여기서 마지막 부등식은 \(i_k\)가 서로 중복되지 않는다는 것에서 유추할 수 있습니다. 이것들을 모두 조합하면 정리의 명제를 보일 수 있습니다. ■

마치며

이것으로 온라인 이분 매칭에 가중치를 추가한 경우에는 문제가 어떻게 바뀌는지에 대해서 알아 보았습니다. 임의의 가중치를 허용하는 온라인 가중치 이분 매칭은 경쟁적으로 풀기 매우 어렵다는 것을 보였는데요. 그 때문에 다양한 변종이 존재하고, 그중 가장 유명한 자유 처분이 있는 최대 가중치 매칭 문제를 소개하였습니다. 마지막으로 그 문제는 \(\frac{1}{2}\)의 경쟁비를 갖는 결정론적 알고리즘이 존재한다는 것도 살펴 보았습니다.

 

본문에서 보이지는 않았지만 알고리즘 1의 경쟁비는 결정론적 알고리즘으로 도달할 수 있는 최선의 결과입니다. 그렇다면 랜덤 알고리즘을 허용하는 경우에는 어떻게 될까요? 앞에서 봤던 일반적인 경우처럼 도움이 되지 않을까요? 놀랍게도 최근 그보다 좋은 경쟁비를 기대할 수 있는 랜덤 알고리즘이 발표되었습니다. 한번 읽어 봤는데 매우 흥미로웠습니다. 개인적으로도 좀더 발전시킬 수 있는 방안이 있을 것으로 보여서 요새는 이를 주제로 연구하고 있기도 합니다. 난이도가 상당해서 블로그에 포스트할 수 있을지는 모르겠습니다. 대신 참조를 남겨 놓을테니 궁금하신 분들은 직접 읽어 보시기를 추천 드립니다.

 

글에 오류가 있거나, 궁금하신 점이 있으시면 알려 주세요. 읽어 주셔서 고맙습니다.

참조

[1] Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, Morteza Zadimoghaddam: Edge-Weighted Online Bipartite Matching. FOCS 2020: 412-423

주석

[ㄱ] 또다른 경쟁비의 정의에 따라서는 어떤 특정한 상수 \(c\)에 대해 \(\rho \cdot \mathsf{OPT} - c\)보다 크거나 같으면 \(\rho\)의 경쟁비를 갖는다고 말합니다. 하지만 본문의 식의 우변에 모두 \(c\)를 빼 주어도 결국 동일한 경쟁비의 상한을 얻게 됩니다.

 

[ㄴ] 마찬가지로 어떤 특정한 상수 \(c\)에 대해 \( \rho \cdot \mathsf{OPT} + c \)보다 작거나 같으면 \(\rho\)의 경쟁비를 갖는다고 말합니다. 이번에는 알고리즘이 출력하는 가중치가 최대 1이므로 충분히 큰 \(c\)에 대해서는 보다 좋은 \( \rho\)를 얻을 수도 있을 것입니다. 하지만 그러기는 쉽지 않겠습니다. 완벽하게 증명을 기술해 본 것은 아니어서 완전히 확신하는 것은 아니지만 다음과 같은 방식으로 \(c\)의 효과를 망가뜨릴 수 있을 것입니다. \( |L| = |R| = 2n \)으로 두고, \(L\)과 \(R\)의 \((2k-1)\) 번쨰 정점과 \(2k\) 번째 정점은 본문의 상대방처럼 동작하게 만들고, 나머지 정점 쌍에 대해서는 무한대의 가중치를 둡니다. 의도는 나머지 정점 쌍을 매칭에 넣기에는 비용이 너무 크므로 분명 \((2k-1)\) 번째와 \(2k\) 번째 정점들 내에서 해결을 할 것인데, 이것들이 계속 쌓이다 보면 \(c\)의 효과를 넘어 서는 때가 오는 것을 만든 것입니다.