Five Representative Problems

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Interval Scheduling

Start time과 finish time이 정해진 job이 주어졌을 때, overlap되지 않는 최대의 cardinality를 구하는 문제이다. 예를 들어, 아래 그림에서 overlap되지 않고 최대로 실행될 수 있는 set of jobs은 {b, e, h}이다.

 

 

 

 

 

Weighted Interval Scheduling

위의 문제에서 각 job이 weight를 가지고 실행되는 job의 weight가 최대가 되는 문제이다. 모든 job의 weight를 1로 두면 위의 문제 Interval Scheduling과 같아진다.

 

 

 

 

Bipartite Matchinig

아래 그림의 Bipartite graph(서로 직접 연결이 되지 않는 set이 두 개가 있음)에서 cardinality를 최대화하는 문제이다. 아래 문제에서는 maximum cardinality가 5이다.

 

 

 

 

Independent Set

Graph에서 independent set의 node개수가 최대가 되도록하는 문제이다.

* Independent set : 직접 연결이 되지 않는 node들의 집합

 

 

 

* Vertex cover problem : 모든 edge를 cover할 수 있는 최소의 노드 set을 찾는 문제

=> Maximum independent set problem은 Minimum vertex cover problem을 푸는 것과 같다. (귀류법으로 증명가능)

 

 

Competitive Facility Location

각 노드는 weight를 가지고 있고 두 명의 경쟁자가 있다. 이 때, 각 경쟁자는 번갈아가면서 노드를 선택하고 이미 선택된 노드에서 인접한 노드는 선택할 수 없다. 여기서 두 경쟁자가 얻을 수 있는 최대 점수를 찾는 문제이다.

 

 

 

 

Time complexity

Interval scheduling : Greedy algorithm으로 $nlogn$

Weighted interval scheduling : dynamic programming으로 $nlogn$

Bipartite matching : Ford-Fulkerson algorithm으로 $n^k$

Independenet set : NP-complete 문제

Competitive facility location : PSPACE-complete 문제