This cstheory.SE post gives various randomized approximation algorithms for the set cover problem. Is there a randomized algorithm (which runs in $\mathrm{poly}(n)$ time) for the set cover problem which achieves an approximation ratio of $1$ (with high probability)? Is it possible to achieve such an algorithm, or is this still unknown?
1 Answer
$\begingroup$
$\endgroup$
1
Approximation ratio of 1 means that it outputs an exact solution (so it is not an approximation algorithm but rather an exact algorithm). Set cover is known to be NP-hard, so there is no such polynomial-time randomized algorithm, unless RP = NP.
-
1$\begingroup$ @Steven, good point, thank you. I have revised my answer. $\endgroup$– D.W. ♦Commented Nov 14, 2023 at 18:50