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$ – Chandra Chekuri Feb 22 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 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 at 9:31

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.