3
$\begingroup$

I'm trying to understand the inapproximability of the minimum set cover problem.

The wikipedia page states that it is hard to approximate within a factor of $(1-o(1))\ln n$ and that $n$ refers to the size of the ground set. It references the work of Dinur and Steurer (2013) who state that, for every $\varepsilon>0$, it is NP-hard to approximate min set cover within a factor of $(1-\varepsilon)\ln n$ where $n$ refers to the size of the instance. It seems they don't define what they mean by "size of the instance," but I take that to mean an encoding of the instance (which takes more space than just the size of the ground set).

Would I be correct in saying that set cover is hard to approximate within a factor of $(1-\varepsilon)\ln N$, where $N$ is the size of the ground set plus the sizes of all the subsets? Or, if $N$ is the size of the ground set plus the number of subsets?

$\endgroup$
  • $\begingroup$ The Dinur & Steurer paper provides a citation into the literature for an earlier $(1-o(1)) \ln n$ result: on p.4 they mention an earlier result of Feige. So, you might find it helpful to read Feige's paper to see if it answers your question. $\endgroup$ – D.W. Jul 21 '16 at 19:05
  • $\begingroup$ @D.W. Feige is indeed clearer. He says that $s$ (the number of subsets) is less than $n$ (the number of points to cover) in his reductions. Still not sure what Dinur and Steurer meant though $\endgroup$ – Austin Buchanan Jul 21 '16 at 19:20
5
$\begingroup$

The hardness proof appears in an earlier paper of Moshkovitz, The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover; Dinur and Steurer proved a version of the Projection Games Conjecture, thus completing the NP-hardness proof. Moshkovitz clearly states that $n$ is the size of the universe, and she also assumes that the number of sets is polynomial in $n$.

Feige had proved earlier that if you can approximate set cover better than $\ln n$ then $\mathsf{NP}\subseteq \mathsf{DTIME}(N^{\log\log N})$. He improved on earlier result of Lund and Yannakakis which showed a hardness of $0.72\ln n$ under the same assumption.

The threshold $\ln n$ (where $n$ is the size of the universe) is important since it is achieved by the greedy algorithm. The analysis of the greedy algorithm shows that after $OPT \cdot t$ steps (where $OPT$ is the size of an optimal solution), we have covered a $1-e^{-t}$ fraction of the universe. When $e^{-t} < 1/n$, we have covered the entire universe (since we cover more than $n-1$ elements). Hence after at most $t = OPT \cdot \ln n$ steps, the greedy algorithm manages to cover the entire universe. This is where the dependence on the size of the universe comes from.

$\endgroup$
  • $\begingroup$ So we cannot claim (under current knowledge) that it is NP-hard to get a $(1-\varepsilon)\ln n$ approximation when $s \le n$? $\endgroup$ – Austin Buchanan Jul 21 '16 at 22:04
  • $\begingroup$ Dinur and Steurer don't claim anything. It's all in the paper of Moshkovitz. Perhaps you should take a look at her construction and see for yourself. $\endgroup$ – Yuval Filmus Jul 21 '16 at 22:06
  • $\begingroup$ I corrected the phrasing in my comment. To be clear: per Feige's notation, $s$ is the number of subsets $\endgroup$ – Austin Buchanan Jul 21 '16 at 22:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.