<p>In [1], Feige proves that if there is a polynomial algorithm with approximation ratio in <span class="math-container">$o(\log n)$</span> for any <span class="math-container">$\mathsf{log\textit{-}APX}$</span> hard problem (say Minimum Dominating Set), then <span class="math-container">$\mathsf{NP}\subseteq\mathsf{DTIME}\left(n^{O(\log \log n)}\right)$</span> .</p>
<blockquote>
<p>The paper dates back to 1998. Has any progress been made since this result, i.e., stronger consequences, for example under <span class="math-container">$ETH$</span> or <span class="math-container">$SETH$</span>, or any other plausible conjecture?</p>
</blockquote>
<p>[1] Feige, U. (1998). A threshold of <span class="math-container">$\ln n$</span> for approximating set cover. Journal of the ACM (JACM), 45(4), 634-652.</p>

CC BY-SA 4.0
2021-05-16T15:12:54.790Z
@MaxFlow Thank you for the reference. If you convert your comment to an answer, I would be happy to accept it. However, I read the papers, and they provide a  $(1-\epsilon)(\log n)$ lower bound for Set Cover specifically. Is this bound transferable to any $\log\text{-}\mathsf{APX}$-hard problem? I'm mainly interested by Vertex Cover.
Lamine
CC BY-SA 4.0
2021-05-16T15:17:37.903Z
@ChandraChekuri It is impossible to reply to two users in the same comment. So I kindly ask you the same question as to Max Flow.
Lamine
CC BY-SA 4.0
2021-02-22T23:04:45.273Z
Moshkovitz established ln n hardness of Set Cover under P \neq NP. https://theoryofcomputing.org/articles/v011a007/
Chandra Chekuri
CC BY-SA 4.0
2021-02-23T22:45:32.193Z
@ChandraChekuri Thus any $o(\log n)$ approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem implies $\mathsf{P}=\mathsf{NP}$? If you convert the comment to an answer, I will accept it.
Lamine
CC BY-SA 4.0
2021-02-26T09:31:08.773Z
As mentioned in the abstract of Moshkovitz' paper, ln n hardness of Set Cover specifically under P \neq NP was established already by Dinur and Steurer: http://dx.doi.org/10.1145/2591796.2591884
Max Flow
<complexity-classes><approximation-hardness>
Consequences of an $o(\log n)$-approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem
Lamine
# Consequences of an $o(\log n)$-approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem

(Asked by: username_0 on 2021-02-22)

In [1], Feige proves that if there is a polynomial algorithm with approximation ratio in $o(\log n)$ for any $\mathsf{log\textit{-}APX}$ hard problem (say Minimum Dominating Set), then $\mathsf{NP}\subseteq\mathsf{DTIME}\left(n^{O(\log \log n)}\right)$ .

> The paper dates back to 1998. Has any progress been made since this result, i.e., stronger consequences, for example under $ETH$ or $SETH$, or any other plausible conjecture?

[1] Feige, U. (1998). A threshold of $\ln n$ for approximating set cover. Journal of the ACM (JACM), 45(4), 634-652.

**Tags:** complexity-classes, approximation-hardness
> **Comments:**
> **username_1**: Moshkovitz established ln n hardness of Set Cover under P \neq NP. https://theoryofcomputing.org/articles/v011a007/  
> **username_0**: @ChandraChekuri Thus any $o(\log n)$ approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem implies $\mathsf{P}=\mathsf{NP}$? If you convert the comment to an answer, I will accept it.  
> **username_2**: As mentioned in the abstract of Moshkovitz' paper, ln n hardness of Set Cover specifically under P \neq NP was established already by Dinur and Steurer: http://dx.doi.org/10.1145/2591796.2591884  
> **username_0**: @MaxFlow Thank you for the reference. If you convert your comment to an answer, I would be happy to accept it. However, I read the papers, and they provide a  $(1-\epsilon)(\log n)$ lower bound for Set Cover specifically. Is this bound transferable to any $\log\text{-}\mathsf{APX}$-hard problem? I'm mainly interested by Vertex Cover.  
> **username_0**: @ChandraChekuri It is impossible to reply to two users in the same comment. So I kindly ask you the same question as to Max Flow.  

---

## 0 answers

