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.

  • 5
    $\begingroup$ Moshkovitz established ln n hardness of Set Cover under P \neq NP. theoryofcomputing.org/articles/v011a007 $\endgroup$ Feb 22 '21 at 23:04
  • $\begingroup$ @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. $\endgroup$
    – Lamine
    Feb 23 '21 at 22:45
  • $\begingroup$ 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 $\endgroup$
    – Max Flow
    Feb 26 '21 at 9:31
  • $\begingroup$ @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. $\endgroup$
    – Lamine
    May 16 '21 at 15:12
  • $\begingroup$ @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. $\endgroup$
    – Lamine
    May 16 '21 at 15:17

Your Answer

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

Browse other questions tagged or ask your own question.