Xin-Rong Zheng

Near-Logarithmic Inapproximability of Parameterized Set Cover

We study the approximability of \textnormal{\textsc{Set Cover}} parameterized by the target cover size $k$. Let $n$ be the universe size, $m$ the number of available sets, and $|\Gamma|$ the explicit input length. We prove that, for some absolute constant $c>0$, distinguishing \[ \operatorname{opt}(\Gamma)\le k \quad\t...