3
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.