온라인 알고리즘/Online matching (7) 썸네일형 리스트형 온라인 이분 매칭 경쟁비 상한 (Upper Bound of Competitive Ratio for Online Bipartite Matching) 지난 시간에 우리는 온라인 분수 이분 매칭 문제(online fractional bipartite matching problem)를 \(1-1/e \approx 0.632\)의 경쟁비로 해결하는 결정론적 알고리즘(deterministic algorithm)인 물 채우기 알고리즘(water-filling algorithm)을 공부하였습니다. 온라인 분수 이분 매칭 (Online Fractional Bipartite Matching) 우리에게 처리해야 할 작업들이 있다고 해 보겠습니다. 다만 작업들은 처음부터 주어지지 않고 시간이 흐르면서 하나씩 도착합니다. 작업을 처리하기 위해 우리는 최대 하나의 작업을 할당받을 gazelle-and-cs.tistory.com 아래 본문의 정의와 기호는 이전 글의 것과 동.. 온라인 분수 이분 매칭 (Online Fractional Bipartite Matching) 우리에게 처리해야 할 작업들이 있다고 해 보겠습니다. 다만 작업들은 처음부터 주어지지 않고 시간이 흐르면서 하나씩 도착합니다. 작업을 처리하기 위해 우리는 최대 하나의 작업을 할당받을 수 있는 기계를 몇 대 갖고 있습니다. 문제는 각 작업마다 해당 작업을 처리할 수 있는 기계가 따로 정해져 있다는 것이며, 심지어 어느 기계에서 처리될 수 있는지는 해당 작업이 도착해야 알 수 있다는 점입니다. 우리는 매번 작업이 도착할 때마다 이 작업을 어떤 기계에 할당할지, 그리고 만약 할당한다면, 어느 가용한 기계에 할당하여 줄지를 바로 결정하여야 합니다. 여기서 어려운 점은 이 결정을 후일 번복할 수 없다는 것입니다. 이런 환경에서 작업이 모두 도착했을 때 최대한 많은 작업을 처리하는 것이 목표입니다. 이는 유명한 .. 온라인 메트릭 이분 매칭 (Online Metric Bipartite Matching) 지난 포스트에서는 온라인 가중치 이분 매칭(online weighted bipartite matching)에 대해서 알아 보았습니다. 이 문제에서는 택시에 대한 정보는 미리 알고 있으며, 승객의 정보는 시간이 흐르면서 한 명씩 들어옵니다. 매 순간 어떤 승객의 정보가 알려질 때마다 우리는 이 승객을 택시에 할당할지 말지를 결정해야 하며, 만약 할당한다면 어느 택시에 태울지도 결정해야 합니다. 지난 포스트에서는 언젠가 승객을 어떤 택시에 할당했을 때 이를 더이상 번복할 수 없다면 좋은 경쟁비(competitive ratio)를 얻을 수 없다는 것을 확인하였습니다. 자세한 사항은 이전 포스트를 참고하시기 바랍니다. 2021.02.14 - [온라인 알고리즘/Online matching] - 온라인 가중치 이분.. 온라인 가중치 이분 매칭 (Online Weighted Bipartite Matching) 저번 글에서는 온라인 이분 매칭 문제(online bipartite matching problem)가 무엇인지 설명하고 이를 경쟁적으로 해결하는 알고리즘에 대해서 알아 보았습니다. 문제를 간략히 다시 소개하도록 하겠습니다. 처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 태운 적이 없는 택시 가운데 하나를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 매번 바로 결정해야 한다. 이 결정은 차후에 번복될 수 없다. 이때, 최대한 많은 승객을 태우시오. 위 예시에서 한 가지 현실과는 약간 동떨어진 점이 있다면 바로 건당 정액을 받는 수익 .. 온라인 이분 매칭 랭킹 알고리즘 (Ranking Algorithm for Online Bipartite Matching) 지난번에 온라인 이분 매칭 문제(online bipartite matching problem)에 대해서 알아 보았습니다. 그 문제는 다음과 같이 정의되었습니다. 처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 한 명도 태우지 않은 택시 가운데 한 대를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 바로 결정해야 한다. 이 결정은 번복될 수 없다. 이때 목표는 승객을 최대한 많이 태우는 것이다. 저번 글에서 공부한 내용을 요약하면 다음과 같습니다. 승객이 매번 들어올 때마다 가능한 택시 중 아무 하나에 이 승객을 태우는 방법은 1/2의 .. 온라인 이분 매칭 (Online Bipartite Matching) 어떤 그래프에서 서로 정점을 공유하지 않는 간선의 부분집합을 우리는 매칭(matching)이라고 부릅니다. 매칭의 모양을 살펴보면, 각 정점이 최대 하나의 다른 정점과 짝지어진 꼴입니다. 이를 통해 왜 이러한 간선의 부분집합에 매칭이라는 이름이 붙었는지를 쉽게 유추할 수 있죠. 어떤 그래프가 주어졌을 때, 크기가 작은 매칭을 찾는 것은 간단합니다. 정의에 따르면 아무 간선을 고르지 않는 방법도 가능한 매칭이기 때문이죠. 따라서 대개 우리는 크기가 가장 큰 매칭을 찾고자 하죠. 이 문제를 우리는 최대 매칭 문제(maximum matching problem)이라고 부릅니다. 이 문제는 실생활에서 발생할 수 있는 여러 문제들을 효과적으로 나타냅니다. 이미 제 블로그의 다른 글들을 통해 이에 대한 다양한 예시를.. 검색 엔진 회사가 검색어로 수익을 내는 방법 (Ad-Auctions Problem) 물론 그 외에도 다양한 방안이 있겠지만, 다음이나 네이버와 같은 검색 엔진(search engine) 회사들이 수익을 내는 가장 기본적인 방법은 광고입니다. 하지만 이들의 광고 방식은 정해진 지면에 싣거나 정해진 시간에 방송하는 전통적인 광고와는 다른 점이 있죠. 바로 각 사용자의 정보를 알고 이를 토대로 각각에게 알맞는 광고를 보여줄 수 있다는 것입니다. 이들이 활용할 수 있는 정보는 매우 다양하지만, 그 중에서도 검색 엔진 회사가 가장 쉽게 이용할 수 있는 것은 사용자의 검색어입니다. 사용자가 어떤 특정한 검색어를 입력하면, 해당 검색어에 알맞는 광고를 보여주는 것이죠. 여러분들도 검색 엔진에서 무언가를 찾을 때 이와 연관된 광고가 결과 페이지에 함께 나타나는 것을 본 경험이 있을 것입니다. 회사마다.. 이전 1 다음
