35.3 The set-covering problem

35.3-1

Consider each of the following words as a set of letters: $\{\text{arid}$, $\text{dash}$, $\text{drain}$, $\text{heard}$, $\text{lost}$, $\text{nose}$, $\text{shun}$, $\text{slate}$, $\text{snare}$, $\text{thread}\}$. Show which set cover $\text{GREEDY-SET-COVER}$ produces when we break ties in favor of the word that appears first in the dictionary.

(Omit!)

35.3-2

Show that the decision version of the set-covering problem is $\text{NP-complete}$ by reducing it from the vertex-cover problem.

(Omit!)

35.3-3

Show how to implement $\text{GREEDY-SET-COVER}$ in such a way that it runs in time $O\Big(\sum_{S \in \mathcal F} |S|\Big)$.

(Omit!)

35.3-4

Show that the following weaker form of Theorem 35.4 is trivially true:

$$|\mathcal C| \le |\mathcal C^*| \max\{|S|: S \in \mathcal F\}.$$

(Omit!)

35.3-5

$\text{GREEDY-SET-COVER}$ can return a number of different solutions, depending on how we break ties in line 4. Give a procedure $\text{BAD-SET-COVER-INSTANCE}(n)$ that returns an $n$-element instance of the set-covering problem for which, depending on how we break ties in line 4, $\text{GREEDY-SET-COVER}$ can return a number of different solutions that is exponential in $n$.

(Omit!)