매칭 (5) 썸네일형 리스트형 온라인 이분 매칭 경쟁비 상한 (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) 우리에게 처리해야 할 작업들이 있다고 해 보겠습니다. 다만 작업들은 처음부터 주어지지 않고 시간이 흐르면서 하나씩 도착합니다. 작업을 처리하기 위해 우리는 최대 하나의 작업을 할당받을 수 있는 기계를 몇 대 갖고 있습니다. 문제는 각 작업마다 해당 작업을 처리할 수 있는 기계가 따로 정해져 있다는 것이며, 심지어 어느 기계에서 처리될 수 있는지는 해당 작업이 도착해야 알 수 있다는 점입니다. 우리는 매번 작업이 도착할 때마다 이 작업을 어떤 기계에 할당할지, 그리고 만약 할당한다면, 어느 가용한 기계에 할당하여 줄지를 바로 결정하여야 합니다. 여기서 어려운 점은 이 결정을 후일 번복할 수 없다는 것입니다. 이런 환경에서 작업이 모두 도착했을 때 최대한 많은 작업을 처리하는 것이 목표입니다. 이는 유명한 .. 온라인 이분 매칭 랭킹 알고리즘 (Ranking Algorithm for Online Bipartite Matching) 지난번에 온라인 이분 매칭 문제(online bipartite matching problem)에 대해서 알아 보았습니다. 그 문제는 다음과 같이 정의되었습니다. 처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 한 명도 태우지 않은 택시 가운데 한 대를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 바로 결정해야 한다. 이 결정은 번복될 수 없다. 이때 목표는 승객을 최대한 많이 태우는 것이다. 저번 글에서 공부한 내용을 요약하면 다음과 같습니다. 승객이 매번 들어올 때마다 가능한 택시 중 아무 하나에 이 승객을 태우는 방법은 1/2의 .. 온라인 이분 매칭 (Online Bipartite Matching) 어떤 그래프에서 서로 정점을 공유하지 않는 간선의 부분집합을 우리는 매칭(matching)이라고 부릅니다. 매칭의 모양을 살펴보면, 각 정점이 최대 하나의 다른 정점과 짝지어진 꼴입니다. 이를 통해 왜 이러한 간선의 부분집합에 매칭이라는 이름이 붙었는지를 쉽게 유추할 수 있죠. 어떤 그래프가 주어졌을 때, 크기가 작은 매칭을 찾는 것은 간단합니다. 정의에 따르면 아무 간선을 고르지 않는 방법도 가능한 매칭이기 때문이죠. 따라서 대개 우리는 크기가 가장 큰 매칭을 찾고자 하죠. 이 문제를 우리는 최대 매칭 문제(maximum matching problem)이라고 부릅니다. 이 문제는 실생활에서 발생할 수 있는 여러 문제들을 효과적으로 나타냅니다. 이미 제 블로그의 다른 글들을 통해 이에 대한 다양한 예시를.. 텃의 정리 (Tutte's Theorem) 드넓은 황야에 위치한 초원 대학교의 컴퓨터과학과 소속 폰가젤 교수는 2인 조별 과제를 내는 것을 좋아합니다. 혼자서 해결하기에는 벅찬 문제를 두 명이서 협력하여 해결한다면 학생들에게 협동심은 물론 위기에 굴복하지 않는 능력을 기를 수 있다고 굳게 믿기 때문이죠. 물론 '조별과제 잔혹사'라는 말을 언젠간 들어 봤을 정도로 학생들의 원성이 자자하다는 사실도 잘 알고 있습니다. 그가 개설했던 알고리즘 수업의 강의 평가를 보면 쉽게 유추할 수 있었죠. 그동안은 학생들이 자율적으로 조를 편성하도록 놔두었는데, 이러니 어떤 학생들은 전혀 마음이 맞지 않는 사람과 조를 이루어야 하는 불상사가 발생했었죠. 이 부분이 바로 학생들이 가장 불편을 느낀 부분이었습니다. 이번 학기에 가젤 교수는 이러한 학생들의 원성을 잠재우.. 이전 1 다음
