0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @Steven, good point, thank you. I have revised my answer. $\endgroup$
    – D.W. ♦
    Commented Nov 14, 2023 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.