본문 바로가기

온라인 알고리즘

 (17)
온라인 이분 매칭 경쟁비 상한 (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) 우리에게 처리해야 할 작업들이 있다고 해 보겠습니다. 다만 작업들은 처음부터 주어지지 않고 시간이 흐르면서 하나씩 도착합니다. 작업을 처리하기 위해 우리는 최대 하나의 작업을 할당받을 수 있는 기계를 몇 대 갖고 있습니다. 문제는 각 작업마다 해당 작업을 처리할 수 있는 기계가 따로 정해져 있다는 것이며, 심지어 어느 기계에서 처리될 수 있는지는 해당 작업이 도착해야 알 수 있다는 점입니다. 우리는 매번 작업이 도착할 때마다 이 작업을 어떤 기계에 할당할지, 그리고 만약 할당한다면, 어느 가용한 기계에 할당하여 줄지를 바로 결정하여야 합니다. 여기서 어려운 점은 이 결정을 후일 번복할 수 없다는 것입니다. 이런 환경에서 작업이 모두 도착했을 때 최대한 많은 작업을 처리하는 것이 목표입니다. 이는 유명한 ..
최적 페이지 교체 알고리즘 (Optimal Page Replacement Algorithm) 삼 년 전, 저는 유명한 온라인 최적화(online optimization) 문제 중 하나인 온라인 캐싱(online caching)을 소개하고, 이를 해결하는 유명한 방법인 LRU(least recently used) 알고리즘의 경쟁성을 증명하였습니다. [캐싱 / Caching] LRU는 얼마나 좋은 알고리즘일까? 세세한 부분을 많이 놓치기는 하겠지만, 간략히 말해 컴퓨터는 다음과 같이 동작합니다. 메모리에서 데이터를 프로세서로 가지고 와서 사칙 연산, 대소 비교 등과 같이 어떠한 작업을 수행한 다 gazelle-and-cs.tistory.com 글의 서론에서 저는 캐시 미스가 발생했을 때 캐시 메모리 상에서 가장 마지막에 사용되는 자료를 삭제하는 정책인 LFD(longest forward distan..
LRU보다 좋은 페이지 교체 알고리즘 (Randomized Marking Algorithm) 캐시 메모리(cache memory)는 프로세서와 주 메모리 사이에 위치한 용량은 작지만 속도는 빠른 저장 장치를 의미합니다. 이 장치의 용도는 어떤 프로세스가 동작할 때 많이 접근하는 자료를 저장해 두는 것이죠. 프로세스가 특정한 자료를 필요로 할 때 해당 자료가 최신의 상태로 캐시 메모리에 존재한다면, 주 메모리에 직접 접근하지 않고 캐시 메모리에 접근하여 자료를 가져옴으로써 상당한 시간적 이득을 꾀할 수 있습니다. 프로세스가 호출하는 자료의 단위를 페이지(page)라고 부르겠습니다. 만약 프로세스가 어떤 페이지를 필요로 하는데, 최신의 해당 페이지가 캐시 메모리에 존재하는 때를 캐시 히트(cache hit), 그렇지 않을 때를 캐시 미스(cache miss)라고 부릅니다. 전자의 경우에는 캐시 메모..
예측이 있는 스키 대여 문제 (Ski Rental Problem with Predictions) 온라인 문제(online problem)의 대표격인 스키 대여 문제(ski rental problem)는 지난 수십 년간 깊이 그리고 널리 연구되어 온 매우 유서 깊은 문제입니다. 제 블로그에서도 비중 있게 다룬 적이 있는데요. 문제는 다음과 같이 정의됩니다. 우리는 스키장이 문을 닫을 때까지 스키를 타고 싶어 합니다. 스키를 타는 방법은 두 가지로, 하나는 1 원으로 스키를 하루 대여하는 것이고, 다른 하나는 \(B\) 원으로 스키를 구매하는 것입니다. 당연히 언젠가 스키를 대여하면 다음날에는 또 스키를 대여하든지 구매하든지 하여야 하며, 언젠가 스키를 구매하면 더 이상 그런 고민을 할 필요가 없어집니다. 이때 최소의 비용으로 스키장이 문을 닫을 때까지 스키를 타는 것이 문제의 목표입니다. 만약 스키장..
온라인 메트릭 이분 매칭 (Online Metric Bipartite Matching) 지난 포스트에서는 온라인 가중치 이분 매칭(online weighted bipartite matching)에 대해서 알아 보았습니다. 이 문제에서는 택시에 대한 정보는 미리 알고 있으며, 승객의 정보는 시간이 흐르면서 한 명씩 들어옵니다. 매 순간 어떤 승객의 정보가 알려질 때마다 우리는 이 승객을 택시에 할당할지 말지를 결정해야 하며, 만약 할당한다면 어느 택시에 태울지도 결정해야 합니다. 지난 포스트에서는 언젠가 승객을 어떤 택시에 할당했을 때 이를 더이상 번복할 수 없다면 좋은 경쟁비(competitive ratio)를 얻을 수 없다는 것을 확인하였습니다. 자세한 사항은 이전 포스트를 참고하시기 바랍니다. 2021.02.14 - [온라인 알고리즘/Online matching] - 온라인 가중치 이분..
온라인 가중치 이분 매칭 (Online Weighted Bipartite Matching) 저번 글에서는 온라인 이분 매칭 문제(online bipartite matching problem)가 무엇인지 설명하고 이를 경쟁적으로 해결하는 알고리즘에 대해서 알아 보았습니다. 문제를 간략히 다시 소개하도록 하겠습니다. 처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 태운 적이 없는 택시 가운데 하나를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 매번 바로 결정해야 한다. 이 결정은 차후에 번복될 수 없다. 이때, 최대한 많은 승객을 태우시오. 위 예시에서 한 가지 현실과는 약간 동떨어진 점이 있다면 바로 건당 정액을 받는 수익 ..
동적, 스트리밍, 온라인 알고리즘 비교 (Dynamic, Streaming, and Online Algorithm) 최근, 저널에 제출했던 논문에 대한 심사 결과를 받았습니다. 논문의 주제는 온라인 알고리즘인데 스트리밍 알고리즘에 대한 문헌 검토가 부족하니 이를 보충하라는 평가를 받았습니다. 논문을 쓸 때 참조했던 다른 논문들에서는 스트리밍 알고리즘에 대한 내용을 발견하지 못했었는데 이런 평가를 받아서 처음에는 적잖이 당황했습니다. 그런데 이 내용들을 공부해 보니 서로 비슷하면서도 다른 특징들이 있더군요. 우리말로 적힌 자료는 찾기 어려웠어서, 제 공부를 겸해 이번에 알게 된 내용들을 여기에 정리하고자 합니다. 아래 내용을 미리 요약을 하자면 다음과 같습니다. 동적 알고리즘(dynamic algorithm)은 입력에 무언가 추가되거나 삭제되는 등의 수정(update)이 발생하며 그때마다 바뀐 입력에 맞는 올바른 답을 ..
온라인 이분 매칭 랭킹 알고리즘 (Ranking Algorithm for Online Bipartite Matching) 지난번에 온라인 이분 매칭 문제(online bipartite matching problem)에 대해서 알아 보았습니다. 그 문제는 다음과 같이 정의되었습니다. 처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 한 명도 태우지 않은 택시 가운데 한 대를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 바로 결정해야 한다. 이 결정은 번복될 수 없다. 이때 목표는 승객을 최대한 많이 태우는 것이다. 저번 글에서 공부한 내용을 요약하면 다음과 같습니다. 승객이 매번 들어올 때마다 가능한 택시 중 아무 하나에 이 승객을 태우는 방법은 1/2의 ..
스키 대여 문제의 경쟁비 하한 (Lower Bound of Competitive Ratio for Ski Rental) 스키 대여 문제(ski rental problem)는 대표적인 온라인 문제(online problem) 중 하나입니다. 이 문제에서는 스키장이 언제 폐장할지 모르는 상황에서 우리는 매일 스키를 대여하거나 구매해야 합니다. 한번 스키를 구매하면 이후 계속 사용할 수 있지만 대여를 하면 당일만 사용할 수 있습니다. 이 문제의 목표는 최소의 비용으로 폐장할 때까지 스키를 타는 방법을 찾는 것입니다. 이전 글에서는 이 문제를 결정론적(deterministic)으로 해결하는 2-경쟁 알고리즘(competitive algorithm)이 존재하고, 해당 경쟁비가 결정론적 알고리즘으로서는 이룰 수 있는 최선의 결과라는 것을 보였습니다. 2020/03/15 - [온라인 알고리즘/Ski rental] - [스키 대여 문제..

티스토리툴바