4
$\begingroup$

Feige's well known result (and more recent results) show that set cover cannot be approximated within a factor of $(1 - o(1)) \ln n$, where $n$ is the number of variables. What if we want an approximation ratio in terms of $\log m$?

Apparently, there is a folklore result that the approximation ratio must be of the form $\Omega(\log m)$. (The reason for this is that one can assume that the set cover instances which witness the hardness result of Feige, satisfy $m = \text{poly}(n)$). Does anyone know an actual reference for this result? All the sources I read merely state that this is "well-known."

Is there anything more specific known about the approximation ratio here? For instance, is it known what is the optimal constant coefficient of $\log m$ in the approximation ratio?

Any sources/references would be greatly appreciated

$\endgroup$
1

0

Your Answer

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

Browse other questions tagged or ask your own question.