Approximation Algorithms (2)

Set-Covering Problem

Set-Covering Problem

Set-Covering Problem Formulation

• A finite set $X$
• A family $F$ of subsets of $X$
• $X=\cup_{S\in F}S$
• Find a minimum size subset $C \sub F$ whose members cover all of $X$ ($C$: set cover)

---

NP-Completeness

Reduction in polynomial time

• Given a graph $G=(V,E)$ and integer $k$, define $X=E$ and $F=V$
  

---

Approximation

A simple greedy heuristic with a logarithmic approximation ratio

• 남은 vertex 중 가장 많은 vertex 를 커버하는 Set 선택

---

Time complexity

• $S$ 의 원소 개수는 최대 $X$ 개, $S$ 의 개수는 $F$ 개

---

Proof

• Let $S_i$ be the $i$-th subset selected by Greedy-Set-Cover
• $S_i$ 가 선택될 때마다 cost 1 을 assign, 처음으로 선택되는 element 들에 cost 분산해줌
• Element $x$ 가 $S_i$ 에 의해 처음 선택된 경우 cost $c_x$
  
  • $S_i$ 에서 처음으로 선택된 element 개수의 역수
• 알고리즘의 매 step 마다 cost 1을 할당하기 때문에 $|C|=\displaystyle\sum_{x \in X}c_x$
• Cost assigned to the optimal cover $C^*$ is $\displaystyle\sum_{S \in C^*}\sum_{x \in S}c_x$
• Each $x \in X$ is in at least one set $s \in C^*$, $\displaystyle\sum_{S \in C^*}\sum_{x \in S}c_x \geq \sum_{x \in X}c_x$
  • $C^*$ 의 set $S_i$ 에 $x$ 가 여러번 포함될 수 있기 때문에
• $\therefore |C| \leq \displaystyle\sum_{S \in C^*}\sum_{x \in S}c_x$