patternMinor
Clarification on the inapproximability of set cover
Viewed 0 times
clarificationtheinapproximabilitycoverset
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#60846, answer score: 5
Revisions (0)
No revisions yet.