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!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用