# Consequences of an $o(\log n)$-approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem

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.

• Moshkovitz established ln n hardness of Set Cover under P \neq NP. theoryofcomputing.org/articles/v011a007 Feb 22 '21 at 23:04
• @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. Feb 23 '21 at 22:45
• 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: dx.doi.org/10.1145/2591796.2591884 Feb 26 '21 at 9:31
• @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. May 16 '21 at 15:12
• @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. May 16 '21 at 15:17