Sep 2026
Near-Logarithmic Inapproximability of Parameterized Set Cover
It is shown that for every $\gamma=o(\frac{\log N}{\log\log N})$, $\gamma$-gap $k$-SetCover is W[1]-hard even when $d=O(k^{2}\gamma\log(k\gamma)) and $d^*=O(k\gamma)$.
Bing-Kai Lin, Xin-Rong Zheng
· arXiv.org · 1 citation