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

Photo by Lexi Ruskell on Unsplash

어떤 그래프에서 서로 정점을 공유하지 않는 간선의 부분집합을 우리는 매칭(matching)이라고 부릅니다. 매칭의 모양을 살펴보면, 각 정점이 최대 하나의 다른 정점과 짝지어진 꼴입니다. 이를 통해 왜 이러한 간선의 부분집합에 매칭이라는 이름이 붙었는지를 쉽게 유추할 수 있죠. 어떤 그래프가 주어졌을 때, 크기가 작은 매칭을 찾는 것은 간단합니다. 정의에 따르면 아무 간선을 고르지 않는 방법도 가능한 매칭이기 때문이죠. 따라서 대개 우리는 크기가 가장 큰 매칭을 찾고자 하죠. 이 문제를 우리는 최대 매칭 문제(maximum matching problem)이라고 부릅니다.

 

이 문제는 실생활에서 발생할 수 있는 여러 문제들을 효과적으로 나타냅니다. 이미 제 블로그의 다른 글들을 통해 이에 대한 다양한 예시를 보여드렸습니다만, 오늘의 주제와 관련이 있을 다른 예시를 하나 더 소개하겠습니다. 이번에는 여러분이 한 콜택시 회사를 운영한다고 해보겠습니다. 택시는 승객을 태워 목적지까지 바라다주는 것으로 수익을 올립니다. 여기서 여러분 회사는 운행 거리에 상관 없이 건당 정해진 금액을 받는 수익 모델로 유명하다고 합시다.(그러한 수익 모델을 갖고 있는 회사가 있는지는 잘 모르겠습니다.) 따라서 최대한 많은 수의 승객을 택시와 연결해 주어야 회사가 높은 수익을 올릴 수 있을 겁니다. 각 승객은 현재 위치, 목적지 등 서로 다른 상황에 놓여 있으며, 이는 택시도 마찬가지입니다. 따라서 각 승객을 태워줄 수 있는 택시가 따로 정해집니다. 여러분 회사는 콜택시 회사이므로 당연히 승객 한 명을 택시 한 대에 할당하면 해당 택시에는 다른 승객을 태울 수 없습니다. 과연 승객을 택시에 어떻게 할당하면 최대한 큰 수익을 올릴 수 있을까요?

 

만약 우리에게 승객의 정보와, 택시의 정보, 그리고 각 승객마다 어떤 택시를 연결해 줄 수 있는지에 대한 정보가 처음부터 모두 주어진다면 위 문제를 최대 매칭 문제로 해결할 수 있다는 것을 쉽게 알 수 있습니다. 그중에서도 이 문제는 특히 주어지는 그래프가 이분 그래프(bipartite graph)인 최대 이분 매칭 문제(maximum bipartite matching problem)로 표현됩니다. 이 문제를 해결하는 방법은 다양합니다. 개중에서 가장 유명한 방법을 제 블로그에서 포스팅한 적이 있으니 궁금하신 분들은 아래를 참조하시기 바랍니다.

2020/02/22 - [조합론적 최적화/Matching] - 호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm)

호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm)

위 예시가 최대 이분 매칭 문제에 관한 흥미로운 통찰을 제공하는 것은 사실이지만 지나치게 단순화된 면도 있다는 사실을 여러분들도 쉽게 납득하실 겁니다. 다양한 부분이 그러한 면모를 보이지만, 그중에서도 가장 말이 되지 않는 가정은 모든 승객에 대한 정보를 갖는다는 것입니다. 택시는 여러분의 회사에서 운용을 하는 것이므로 모든 정보를 갖고 있다는 점이 전혀 이상할 것 없지만, 승객은 그렇지 않습니다. 어느 승객이 언제 어느 위치에서 어디로 가고 싶은지를 미리 정확히 알기는 불가능하기 때문입니다.

 

따라서 해당 가정을 다음과 같이 풀어준 문제를 생각해 보도록 하겠습니다. 맨 처음 여러분에게는 각 택시에 대한 정보만 있습니다. 승객은 시간이 흐르면서 한 명 씩 들어오게 되는데, 그때마다 (그리고 그제야) 승객에 대한 정보와 연결해줄 수 있는 택시들에 대한 정보를 알게 됩니다. 승객은 당연히 기다리는 것을 싫어하죠. 그러므로 여러분은 이 승객을 바로 가능한 택시 중 하나에 태우든지 아니면 태울 수 없다고 알려 주든지 해야 합니다. 만약 짝이 지어지면 이후에는 번복할 수 없습니다. 승객을 태웠는데 나중에 승객 보고 다른 택시로 갈아 타라고 할 수는 없잖아요? 또, 태울 수 없다고 알려 줬는데 나중에 다시 태울 수도 없습니다. 이미 승객은 경쟁사의 콜택시를 타고 유유히 목적지로 향하고 있을 것입니다. 여러분의 목표는 미래를 전혀 알 수 없고, 한 번 결정이 된 것은 나중에 다시 바뀔 수 없는 이러한 상황에서 최대의 수익을 올리는 것입니다. 과연 어떻게 하면 최대한 많은 돈을 벌 수 있을까요?

 

이 문제가 바로 이번 시간에 함께 고민해 볼 온라인 이분 매칭 문제(online bipartite matching problem)입니다. 아래에서 소개할 내용을 먼저 간략히 알려드리면 다음과 같습니다.

• 온라인 이분 매칭을 \(1/2\)의 경쟁비(competitive ratio)로 해결하는 결정론적(deterministic) 알고리즘이 존재한다.
• 온라인 이분 매칭을 해결하는 어떠한 결정론적 알고리즘도 \(1/2\)보다 좋은 경쟁비를 가질 수는 없다.
• 승객이 들어왔을 때 가능한 택시들 중에서 하나를 균등한 확률(uniformly at random)로 뽑아서 할당하는 확률적 알고리즘(randomized algorithm)은 \(1/2\)의 경쟁비를 갖는다.

아래 내용은 온라인 알고리즘(online algorithm)을 분석하는 방법을 알고 있다는 가정 아래에서 작성되었습니다. 해당 방법을 잘 모르시는 경우에는 다음 글을 읽어 보시는 것을 추천드립니다.

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

온라인 알고리즘 (Online Algorithm)

간단한 탐욕 알고리즘의 경쟁비

먼저 다음과 같이 매우 간단한 탐욕 알고리즘(greedy algorithm)을 생각해 보겠습니다.

매번 승객이 들어오면, 아직 아무 승객도 태우지 않은 택시 중 이번 승객을 태울 수 있는 택시가 있으면 그중 아무 택시에 이번 승객을 태운다. 만약 가능한 택시가 없으면 승객에게 태울 수 없다고 알린다.

놀랍게도 우리는 이렇게 간단한 알고리즘이 \(1/2\)의 경쟁비를 갖는다는 것을 보일 수 있습니다. 바로 다음의 성질 때문이죠.

정리 1. Maximal matching과 maximum matching의 관계

---

임의의 이분 그래프에 대해서, \(M\)을 한 maximal matching, \(M^\star\)를 한 maximum matching이라고 하면, 항상 \( |M| \geq \frac{1}{2} |M^\star| \)를 만족한다.

증명은 생략하겠습니다. 혹시 maximal matching이 무엇인지 잘 모르시거나, 위 정리의 증명이 궁금하신 분들은 아래 제 다른 글을 참조하시기 바랍니다.

2020/05/03 - [수학적 도구/Basic] - Maximal & Maximum

Maximal & Maximum

따라서 우리는 다음과 같은 결론을 이끌어낼 수 있습니다.

정리 2. 탐욕 알고리즘의 경쟁비

---

위 탐욕 알고리즘은 온라인 이분 매칭 문제를 \(1/2\)의 경쟁비로 해결하는 (결정론적) 알고리즘이다.

[증명] 매번 승객이 들어왔을 때, 이 승객을 처리한 다음의 매칭을 \(M\)이라고 하겠습니다. 알고리즘의 성질에 의해 우리는 \(M\)이 maximal matching이라는 사실을 쉽게 알 수 있는데, 만약 그렇지 않다면 분명 이번 시각 이전에 들어온 한 승객(이번에 들어온 승객 포함)에 대해, 연결해 줄 수 있는 택시가 있었음에도 승객을 할당하지 않았다는 것을 의미하게 되고, 이는 이 알고리즘의 동작에 모순이 되기 때문입니다. 정리 1에 의해 maximum matching의 크기에 적어도 절반의 크기를 \(M\)이 가질 것이므로 이 알고리즘은 \(1/2\)의 경쟁비를 갖는다는 것을 알 수 있습니다. ■

결정론적 알고리즘의 경쟁비 상한

더욱 흥미로운 점은 위 절의 탐욕 알고리즘이 결정론적 알고리즘으로 얻을 수 있는 최선의 알고리즘이라는 것입니다. 이전 포스트에서 결정론적 알고리즘의 성능을 분석하기 위해서는 적응형 상대방(adaptive adversary)를 상정하여도 괜찮다는 것을 보인 바 있습니다. 따라서 적응형 상대방을 하나 만들어서 어느 결정론적 알고리즘도 이 상대방을 대항해서는 좋은 경쟁비를 얻을 수 없다는 것을 보이도록 하겠습니다.

정리 3. 결정론적 알고리즘을 망치는 적응형 상대방

---

온라인 이분 매칭 문제를 해결하는 임의의 결정론적 알고리즘에 대해 알고리즘의 최종 매칭의 크기가 maximum matching의 크기에 절반이 넘지 못하게 하는 적응형 상대방이 존재한다.

[증명] 다음과 같이 적응형 상대방을 만들어 보겠습니다. 이 상대방은 먼저 알고리즘에게 두 대의 택시 \(v_1, v_2\)를 제공합니다. 다음, 첫 번째 승객 \(u_1\)이 들어오며 \(u_1\)은 \(v_1, v_2\) 모두와 인접(adjacent)합니다. 그러면 알고리즘의 선택은 다음 세 가지 중 하나입니다.

1. 아무 택시와도 연결하지 않는다.
2. \(v_1\)과 연결한다.
3. \(v_2\)와 연결한다.

만약 1번을 선택하면 상대방은 여기서 입력을 종료합니다. 2번을 선택하면 두 번째 승객 \(u_2\)를 보여주게 되는데, 이때, \( u_2 \)는 \(v_1\)과만 인접하도록 합니다. 반대로 3번을 선택하면 비슷하게 \(u_2\)를 보여주나 이번에는 \(v_2\)와만 인접하도록 만들어 줍니다.

그림 1. 적응형 상대방의 동작 방식. (A), (B), (C)는 각각 알고리즘의 1번, 2번, 3번 선택에 대한 적응형 상대방의 대응을 나타낸다. 검은 실선은 \(v_1\)이, 빨간색 점선이 \(v_2\)가 들어올 때 추가되는 간선이다. 굵은 선은 알고리즘이 이를 매칭에 넣은 것을 의미한다.

알고리즘이 1번을 선택하면 알고리즘의 최종 매칭의 크기는 0입니다. 하지만 maximum matching의 크기는 1이 되죠. 따라서 이 경우 정리의 명제가 바로 성립합을 알 수 있습니다. 다음으로, 2번이나 3번을 선택한 경우에는 알고리즘의 최종 매칭의 크기가 1이라는 사실을 알 수 있습니다. 왜냐하면 두 번째 승객 \(u_2\)가 각각 이미 다른 승객과 연결된 택시와만 인접하기 때문에 \(u_2\)를 짝지어줄 방법이 없기 때문이죠. 따라서 두 경우 모두 maximum matching의 크기는 2이므로 최종 결과가 최댓값의 절반을 넘지 못한다는 것을 보일 수 있습니다. ■

 

정리 3의 적응형 상대방을 잘 활용하면 우리는 어떤 결정론적 알고리즘도 \(1/2\)보다 좋은 경쟁비를 가질 수 없다는 것을 보일 수 있습니다.^ㄱ

균등한 확률로 할당하는 방법의 성능

결정론적 알고리즘은 최악의 경우에도 보장할 수 있는 성능을 척도로 삼기 때문에 과도하게 평가절하되는 경우가 많이 있습니다. 이를 타개할 다양한 방법 중 하나는 확률에 기대는 것입니다. 알고리즘 내부에서 어떠한 확률적인 시행을 거쳐 결정론적 알고리즘을 망쳤던 최악의 상황이 확률적으로는 거의 일어나지 않도록 만들 수 있다면 우리는 결정론적일 때보다 훨씬 좋은 성능을 "기대"할 수 있게 됩니다.

 

기존의 탐욕 알고리즘의 문제는 승객을 택시와 아무렇게(arbitrarily) 짝지을 수 있었다는 점이죠. 따라서 그 대신에 승객이 들어왔을 때 태울 수 있는 택시들 중에서 각각 균등한 확률(uniformly at random)로 하나를 뽑아서 이 택시에 이번 승객을 태우도록 하겠습니다. 이 확률 알고리즘은 과연 기존의 결정론적 알고리즘에 비해 괄목할 만한 성능의 향상을 보이게 될까요?

 

안타깝지만, 이 알고리즘의 경쟁비도 \(1/2\)를 넘지 못합니다. 이 절에서는 이 사실을 분석해 보도록 하겠습니다. 확률 알고리즘을 분석하기 위해서는 대개 무지각형 상대방(oblivious adversary)을 상정합니다. 이 상대방은 입력을 미리 정한 후 알고리즘의 동작에 상관 없이 정해진 대로 하나씩 알고리즘에 입력을 공급하는 양심적인(?) 상대방입니다. 따라서 아래에서는, 위 확률 알고리즘을 망치는 무지각형 상대방 하나를 만들어 보도록 하겠습니다.

 

어떤 자연수 \(d\)에 대해, 이분 그래프 \(G = (L \cup R, E)\)를 다음과 같이 정의합니다.

• 택시에 대응하는 정점 집합 \(L\)은 \(L_1\)과 \(L_2\)로 이루어지며, 각각 \( L_1 := \{ u_1, \cdots, u_d \} \), \( L_2 := \{ u_{d+1}, \cdots, u_{2d} \} \)의 정점을 갖는다.
• 승객에 대응하는 정점 집합 \(R\)은 \( R_1 \)과 \(R_2\)로 나뉘며, 위와 비슷하게 \( R_1 := \{ v_1, \cdots, v_d \} \), \( R_2 := \{v_{d + 1}, \cdots, v_{2d}\} \)의 정점을 갖는다. 
• 간선 \(E\)는 다음 두 가지 종류를 갖는다.
  • 각 \( i = 1, \cdots, 2d \)에 대해, \( (u_i, v_i) \in E \)이다. 이 간선을 주요 간선이라고 부른다.
  • 각 \( i = d+1, \cdots, 2d\)와 \(j = 1, \cdots, d\)에 대해, \( (u_i, v_j) \in E \)이다. 즉, \( L_2 \cup R_1\)만 따로 떼어 놓고 보면 완전 이분 그래프(complete bipartite graph)를 이룬다.

여기서 \(G\)의 최대 매칭은 주요 간선만 모두 넣은 것으로, 그 크기는 \(2d\)입니다.

그림 2. \(d = 3\)일 때의 \(G\)의 예시. 검정색 실선은 주요 간선을 나타낸 것이다.

이제 상대방이 알고리즘에 정보를 어떻게 제공하는지 정의하겠습니다. 먼저 상대방은 알고리즘에 택시 정점 \(L\)을 기본적으로 제공합니다. 그후 승객 정점 \(R\)은 시간이 흐름에 따라 아래 첨자가 커지는 순서로 알고리즘에 입력합니다. 예컨대, \( v_1 \)을 넣은 후 \(v_2\)를 입력하고, 그 다음에는 \(v_3\)가 알고리즘에 들어가는 식인 것이죠. 매번 \(v_i\)가 들어갈 때마다 그에 딸린(incident) 간선도 함께 주어지게 됩니다.

 

이것으로 무지각형 상대방에 대한 정의를 마쳤습니다. 이제 분석을 시작하겠습니다. 매 \(t\)번째 승객을 처리한 후에 알고리즘이 갖고 있는 매칭을 \(M_t\)라고 부르겠습니다. 이는 알고리즘이 어떻게 수행되냐에 따라 달라집니다. 다음 정리는 알고리즘의 최종 출력의 크기를 결정하는데 중요한 성질을 보여줍니다.

정리 4. 알고리즘의 최종 매칭의 크기의 성질

---

알고리즘이 \(v_1\)부터 \(v_d\)까지 들어왔을 때 주요 간선을 사용하여 승객을 택시에 태운 수를 \(x\)라고 하자. 그러면 이 알고리즘의 최종 매칭의 크기는 \( d + x \)이다.

[증명] 먼저, 알고리즘은 매번 승객을 태울 수 있는 택시가 존재하기만 하면 이번 승객을 태울 것이므로, \(|M_d| = d\)라는 사실을 알 수 있습니다. 그중 \(x\) 명의 승객만 주요 간선으로 처리되었으므로, \(d - x\) 대의 택시는 \(L_2\)에서 옵니다. 이후에 들어오는 \(v_{d+1}, \cdots, v_{2d}\)는 반드시 주요 간선으로 연결된 택시, 즉 \(L_2\)의 택시만 탈 수 있으므로 최대(그리고 정확히) \(x\) 명의 승객을 태우게 됩니다. 따라서 최종 매칭의 크기는 \( |M_d| + x = d+x \)가 됩니다. ■

그림 3. \(d = 3\)일 때, \(x = X_d = 2\)이면 \(L_2\)에는 \(d - x = 1\)의 택시만 사용 가능하다.

위 정리를 통해서 우리는 처음 \(d\) 명의 승객들 중 얼마나 많은 승객을 주요 간선을 통해 짝지어 주었느냐가 알고리즘의 성능을 결정하는데 중요한 지표가 된다는 사실을 알 수 있습니다. 따라서 남은 것은 이 값이 높은 확률로 그리 크지 않다는 것을 보이는 것입니다. 직관적으로 생각해 보아도 그렇게 될 것이라고 예상할 수 있습니다. 예를 들어 첫 번째 승객이 주요 간선의 택시를 탈 확률은 \( \frac{1}{d+1} \) 밖에 되지 않기 때문입니다. 문제는 승객들을 높은 확률로 \(L_2\)의 택시에 계속 태우다 보면 결국 \(L_2\)의 택시가 적어지게 되고, 자연스럽게 \(L_1\)의 택시를 탈 확률이 높아질 수도 있다는 점입니다. 다행히도 아무리 그렇게 된다고 하더라도 그 크기가 그렇게 커지지 않는다는 것을 보일 수 있습니다.

 

이를 보이기 위해서 매 \(t = 1, \cdots, d\)에 대해 \(X_t\)를 \(t\)번째 승객이 처리된 후에 \(v_1, \cdots, v_t\) 중 주요 간선을 통해 매칭에 들어간 개수로 정의하겠습니다. 이를 다시 쓰면 \[ X_t := M_t \cap \{ (u_i, v_i) : i = 1, \cdots, t \} \]가 됩니다. \(X_t\)는 \(M_t\)에 의존하는 확률 변수(random variable)이라는 점도 확인하시기 바랍니다. 그러면 다음 정리를 통해 \(X_t\)의 기댓값이 그렇게 커지지 않는다는 것을 보일 수 있습니다.

정리 5. 매칭에 들어가는 주요 간선의 개수

---

임의의 \(t = 1, \cdots, d\)에 대해, \[ \mathbb{E} [ X_t ]  \leq \sum_{i = 1}^t \frac{1}{d - i + 1} \]를 만족한다.

[증명] \(t\)에 대한 수학적 귀납법으로 증명하겠습니다. 먼저 \(t = 1\)일 때, 첫 번째 승객 \(v_1\)이 주요 간선의 택시  \(u_1\)을 탈 확률은 \( \frac{1}{d+1} \leq \frac{1}{d} \)입니다. 따라서 정리의 명제가 성립한다는 것을 알 수 있습니다.

 

이제 어떤 \(t - 1\)에 대해서 정리의 명제가 만족한다고 하겠습니다. 만약 \(v_t\)가 입력되었을 때, \(v_1, \cdots, v_{t - 1}\) 중에서 주요 간선으로 매칭된 것의 개수가 \( k \)라고 하면(즉, \(X_{t - 1} = k\)일 때), \(v_t\)가 \( u_t \)와 연결될 확률은 \[ \frac{1}{d - t + k + 1} \]이 됩니다. 왜냐하면 \(L_2\)에는 \( d - t + k \) 대의 택시가 여유로운 상태이고 추가로 \( u_t \)도 선택될 수 있기 때문입니다. 따라서 우리는 다음과 같은 점화식을 세울 수 있습니다.

\[ \mathbb{E}[X_t] = \sum_{k = 0}^{t - 1} \left[ Pr[X_{t - 1} = k] \cdot \left( k + \frac{1}{d-t+k+1} \right) \right] = \mathbb{E}[X_{t - 1}] + \sum_{k = 0}^{t - 1} \frac{Pr[X_{t - 1} = k]}{d - t + k + 1} \]

여기서 어떤 \(k \geq 0\)에 대해서도 \( d - t +k + 1 \leq d - t + 1 \)이므로 우변의 분모를 다음과 같이 통일하면서 좌변에 유효한 상한을 만들어낼 수 있습니다.

\[ \mathbb{E}[X_t] \leq \mathbb{E}[X_{t - 1}] + \frac{ \sum_{k = 0}^{t - 1} Pr[X_{t - 1} = k]  }{d - t + 1} = \mathbb{E}[X_{t - 1}] + \frac{1}{d -  t + 1} \]

이때, 마지막 등식은 전체 사건의 확률이 1이라는 사실에서 유도되었습니다. 여기서 우변의 \( \mathbb{E}[X_{t - 1}] \)에 귀납 가정(induction hypothesis)을 적용하면 정리의 명제를 이끌어낼 수 있습니다. ■

 

이제 다음 정리에서 처럼 위 확률 알고리즘의 최종 매칭의 크기의 기댓값의 상한을 구할 수 있습니다.

정리 6. 최종 매칭의 크기의 기댓값

---

위 확률 알고리즘의 최종 매칭의 크기의 기댓값은 \( d + H_d \)를 넘지 않는다. 이때, \(H_d := 1 + \frac{1}{2} + \cdots + \frac{1}{d}\)는 \(d\)번째 조화수(harmonic number)이다.

[증명] 정리 4를 통해 알고리즘의 최종 매칭의 크기는 \(d + X_d\)로 표현이 됩니다. 정리 5에 의해 그 기댓값은 \[ \mathbb{E}[d + X_t] \leq d + \sum_{i = 1}^d \frac{1}{d - i + 1} = d + H_d \]를 만족하게 됩니다. ■

 

\( H_d = \Theta(\ln d) \)는 잘 알려진 사실이며, 따라서 \(  \lim_{d \rightarrow \infty} \frac{H_d}{d} = 0 \)도 쉽게 이끌어낼 수 있습니다. 따라서 충분히 큰 \(d\)에 대해 확률 알고리즘의 경쟁비는 \( 1/2 \)에 수렴한다는 것을 알 수 있게 됩니다.^ㄴ

마치며

이번 시간에는 온라인 이분 매칭 문제가 무엇인지 알아 보고, 이를 해결하는 간단한 \(1/2\)-경쟁 결정론적 알고리즘을 소개한 후 그것이 결정론적 알고리즘으로는 최선이라는 사실을 보였습니다. 보다 좋은 성능을 기대하기 위하여 짝지을 수 있는 후보군 중에서 하나를 균일한 확률로 선택하는 간단한 알고리즘도 고민해 보았으나, 안타깝게도 이 알고리즘 역시 \(1/2\)보다 좋은 경쟁비를 갖기 어렵다는 사실을 보일 수 있었습니다.

 

그렇다면 과연 임의의 확률 알고리즘도 똑같이 \(1/2\)보다 좋은 경쟁비를 얻을 수 없을까요? 그렇지 않습니다. 놀랍게도 \(1-1/e\)의 경쟁비를 기대할 수 있는 확률 알고리즘이 존재합니다. 다음 시간에는 이 알고리즘에 대해서 함께 공부해 보도록 하겠습니다.

 

궁금하신 점이 있으시거나, 글 내용에 잘못된 사항이 있으면 알려주시기 바랍니다. 읽어 주셔서 고맙습니다. :)

각주

ㄱ. 엄밀한 정의에 따르면, 어떤 상수 \(c\)에 대해 알고리즘이 출력하는 매칭의 크기가 \( \rho \mathsf{OPT} - c \)보다 크거나 같으면 \(\rho\)의 경쟁비를 갖는다고 말합니다. 따라서 충분히 큰 \(c\)에 대해서는 알고리즘이 해당 상대방을 대항하여 \( 1/2 \)보다 좋은 경쟁비를 갖는다고 말할 수 있습니다. 이를 해결하는 방법은 해당 상대방의 복사본을 여럿 만들고 알고리즘으로 하여금 이 상대방 군(群)을 상대하도록 하는 것입니다. 그러면 충분히 많은 수에 대해서는 상수 \(c\)의 효과를 무력화시킬 수 있습니다.

 

ㄴ. 이 상대방은 ㄱ에서 나타나는 위 절의 상대방이 갖는 문제를 내포하지 않습니다. \(d\)의 크기가 크면 클 수록 \(c\)로 인한 효과는 사라지기 때문입니다.

참조

[1] Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. "An optimal algorithm for on-line bipartite matching." In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pp. 352-358. 1990.