최근에 온라인 광고 플랫폼에서 광고를 유저에게 최적으로 매칭시키는 문제에 대해 관심이 생겨서 관련된 논문들을 찾아보았는데 많은 논문들이 제목에 소개된 논문을 기반으로 하고 있었기 때문에 먼저 읽어보게 되었습니다.
[논문 링크] An Optimal Deterministic Algorithm for Online b-Matching
위의 논문은 아래와 같은 특수한 경우의 online bipartite matching 문제를 합리적인 방법으로 해결하는 방법을 제시하는 것이 주요 목적이었습니다.
문제)
support station 이 여러개 있고 각각은 최대 b명의 client 만을 support 할 수 있습니다.
또한 각 client 들은 support 받을 수 있는 station 들의 목록이 정해져 있습니다.
client 들이 실시간으로 접속할 때, 어떤 전략으로 client 들을 배정해야 가장 많이 배정할 수 있을까요?
우선 client 들이 모두 들어올 때까지 기다렸다가 한꺼번에 배정해 주어도 되는 상황이라면, maximum bipartite matching 을 찾는 문제와 동일한 문제이고 이는 해결책이 잘 알려진 문제가 됩니다.
하지만 이 문제가 어려운 점은 배정을 실시간으로 해야한다는 것인데요. 즉, 나중에 들어올 client 들의 정보가 없는 것입니다.
어떤 전략을 사용해야 합리적으로 위의 문제를 해결할 수 있을까요???
1. 전략을 평가하는 방법?
우선 전략을 평가하는 방법을 적립할 필요가 있겠습니다.
우리가 어떤 전략을 제시하였다고 합시다. 그러면 그 전략이 얼마나 뛰어난지를 어떻게 평가하면 좋을까요?
이 논문에서는 그 방법으로 competitive ratio 라는 지표를 사용하였습니다.
competitive ratio 는 온라인(실시간) 알고리즘을 분석하기 위해 발명된 방법으로, 오프라인(비실시간)으로 문제를 풀어서 나온 최적해와 비교를 하는 방법이고 아래와 같은 방식으로 사용합니다.
어떤 문제를 오프라인으로 문제를 풀어서 얻은 최적해의 값이 $opt$ 였다고 합시가. 이 때, 어떤 온라인 알고리즘의 competitive ratio 가 $r (0 \leq r \leq 1)$ 이라는 것은 온라인 알고리즘이 어떤 최악의 입력에 대해서도 $opt * r$ 이상의 성능을 내는 것이 보장된다는 의미를 가집니다.
2. 알고리즘
이 논문에서 제시한 전략은 아주 간단합니다.
논문에서 BALANCE 라고 명명한 이 알고리즘은 단순히 client 가 접속하면 그 client 들을 배정할 수 있는 support station 중에 자리가 가장 많이 남아있는 곳에 배정하는 것입니다. 자리가 가장 많이 남아있는 station 이 여러곳이라면 아무곳에나 배정하여도 무방합니다.
이 논문에서는 이 간단한 온라인 알고리즘의 competitive ratio 가 $1 - 1/(1 + 1/b)^b$ 라는 것을 증명합니다.
3. upper bound
더 나아가 이 논문에서는 이 문제에 대한 competitive ratio 의 최댓값이 $1 - 1/(1 + 1/b)^b$ 라는 것을 증명하므로써 BALANCE 알고리즘이 최고의 competitive ratio 를 달성한다는 것을 보입니다.
증명은 어떤 알고리즘에 대해서도 최적해의 $1 - 1/(1 + 1/b)^b$ 배 이하의 성능을 보이게 하는 예제를 제시하는 방식으로 서술되어 있습니다.
4. 배운 점
최근들어 현실에서 일어나는 일들을 수학적으로 모델링하여 해결하는 것에 흥미를 가지게 되어서 공부하고 싶다고 생각을 했는데, 그러한 간단한 예시라고 생각되어 아주 재미있었습니다.
또한 온라인 알고리즘의 competitive ratio 를 증명하는 과정과 그 upper bound 를 증명하는 과정을 한꺼번에 볼 수 있어서 의미가 있었고, 온라인 알고리즘을 통상 어떤 방식으로 분석하는지 알 수 있게 된 좋은 시간이었습니다.