Consider the following instance of Set Cover problem:
- Universe U={a,b,c}
- Family F={S1={a,b},S2={a},S3={b},S4={c}}
We build the following DP table for finding the Minimum Set Cover.
Π(X,j) : minimum number of sets from S1,…,Sj required to cover X
| j\X | ϕ | {a} | {b} | {c} | {a,b} | {a,c} | {b,c} | {a,b,c} |
|---|
| 0 | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | 0 | 1 | 1 | ∞ | 1 | ∞ | ∞ | ∞ |
| 2 | 0 | 1 | 1 | ∞ | 1 | ∞ | ∞ | ∞ |
| 3 | 0 | 1 | 1 | ∞ | 1 | ∞ | ∞ | ∞ |
| 4 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | ? |
What is the missing entry?
