The set cover problem is one of Karp's 21 NP-complete problems.
The set cover problem is one of Karp's 21 NP-complete problems. Given a set of elements $$U=\{1,2,...,n\}$$ (called the universe) and a collection $$S$$ of $$k$$ sets whose union equals the universe, and and a cost function $$cost:S\rightarrow Q^+$$, the weighted set cover problem is to identify the smallest cost of sub-collection of $$S$$ whose union equals the universe. Consider an approximation algorithm as follows:
```
C = null
while ( C!=U ) {
for each S[i], calculate the cost-effectiveness a[i] = cost(S[i]) / |S[i]-C|
find the best cost-effective set, say S[j]
pick S[j]
C = C union S[j]
}
output the picked sets
```
If $$P\neq NP$$, we can't find a constant $$\rho\in N^+$$, so that the approximation ratio of the above algorithm is $$\rho$$.
~@[](4)答案：TRUE