# Inapproximability of set cover: can I assume m=poly(n)?

I am trying to show that a certain problem is inapproximable by a reduction from set cover. My reduction transforms an instance with ground set of size $n$ and $m$ sets into an instance of my problem where a certain parameter $r$ is of size $O(n+m)$. I can then show that an instance of set cover where the cover size is s corresponds to an instance of my problem where the size of the optimal solution is $2s$ (or something like this), and vice versa. I would like to invoke Raz-Safra to conclude that my problem is inapproximable up to a factor of $c \log{r}$, for some constant $c$. This would work fine if I could assume that $m$ is bounded by a fixed polynomial of $n$. Does anyone know if it is kosher to assume this? This is certainly true for the family of instances used in the standard NP-hardness proof for set cover, but I am not sure if this remains the case for the kind of PCP reductions employed by Raz and Safra.

• What is the weakest separation assumption that will still yield a $(1-\epsilon)\log n$ hardness ? – Suresh Venkat Oct 1 '11 at 21:00
• @Suresh: I assume you mean $(1-\epsilon)\ln n$. The assumption of Feige ($NP\not\subseteq DTIME(n^{\log\log n})$) and my assumption ("The Projection Games Conjecture") are incomparable. I believe that my assumption would be proved in the foreseeable future. – Dana Moshkovitz Oct 2 '11 at 12:57
• @DanaMoshkovitz: Thanks! I am not sure I understand your first claim, though. What's wrong with the following (hypothetical) reduction: I start with an instance of (say) Vertex Cover with $k$ vertices and create an instance of Set Cover with $m = k^3$ sets and ground set of size $n$, where $n$ is the solution to $n^{\log n} = m$? This definitely works in poly-time. Admittedly, I have never seen a reduction like this, but it does not seem logically impossible. Or am I wrong? Of course, my original question has already been answered, so feel free to ignore this one. I am just curious... – Edith Elkind Oct 2 '11 at 16:20