[COSE214] Matroid

A matroid and greedy algorithms

 

optimization problem의 구조가 matroid라면, 그 문제는 greedy algorithm을 통해 최적해를 찾을 수 있다. 그러나 optimization problem이 greedy algorithm을 통해 해결된다고 해서 해당 문제의 구조가 항상 matroid 인 것은 아니다.

 

Unit task scheduling problem

unit task scheduling problem이란 a1부터 an까지 작업시간이 1이 걸리면서 각각 다른 deadline과 지키지 못했을 때 발생하는 penalties가 존재하는 여러 unit task들이 있을 때, penalties의 합이 최소화 되도록 작업 순서를 설계하는 것을 말한다. 

이러한 unit task scheduling problem은 matroid 구조로 변환하여 greedy algorithm으로 풀 수 있다. 집합 S가 {a1, a2 , … , an } 이고 I를 S의 subsets(x)들의 set이라고 하자. 이 때 x는 penalties의 합계가 0이 되는 활동들의 합으로 구성된다. 

 

 

다음과 같은 예시에서 k+1가 deadline인 task에 대해서 생각해보자. (이 경우에는 deadline이 4인 a4) y의 task 중 가장 늦은 deadline을 가진 task는 k가 deadline 이므로, 이 때 x-y 집합에 k+1이 존재한다면 이를 y에 추가한다고 해도 다른 task와 중복되지 않는다. 따라서 unit task scheduling problem은 matroid 구조를 가지며, greedy algorithm으로 해결할 수 있다.