Tighter inapproximability for set cover

Abstract

Set Cover is a classic NP-hard problem; as shown by Slavík (1997) the greedy algorithm gives an approximation ratio of $\ln n-\ln \ln n+\Theta (1)$. A series of works by Lund \& Yannakakis (1994), Feige (1998), Moshkovitz (2015) have shown that, under the assumption $P\ne NP$, it is impossible to obtain a polynomial-time approximation ratio with approximation ratio $(1-\alpha )\ln n$, for any constant $\alpha >0$. In this note, we show that under the Exponential Time Hypothesis (a stronger complexity-theoretic assumptions than $P\ne NP$), there are no polynomial-time algorithms achieving approximation ratio $\ln n-C\ln \ln n$, where $C$ is some universal constant. Thus, the greedy algorithm achieves an essentially optimal approximation ratio (up to the coefficient of $\ln \ln n$).

We discovered that these results have already appeared in Dinur & Steurer, "Analytical approach to parallel repetition."