# Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems

arXiv: https://arxiv.org/abs/2008.05374 · HTML: https://mlsanity.com/paper/2008.05374/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2020.

## Built on by (most cited first, 1 of 1)

- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)

## Abstract (arXiv)

We show that Set Cover on instances with N elements cannot be approximated within (1-γ)ln N-factor in time exp(Nγ-δ), for any 0 < γ < 1 and any δ > 0, assuming the Exponential Time Hypothesis. This essentially matches the best upper bound known by Cygan et al. (IPL, 2009) of (1-γ)ln N-factor in time exp(O(Nγ)). The lower bound is obtained by extracting a standalone reduction from Label Cover to Set Cover from the work of Moshkovitz (Theory of Computing, 2015), and applying it to a different PCP theorem than done there. We also obtain a tighter lower bound when conditioning on the Projection Games Conjecture. We also treat three problems (Directed Steiner Tree, Submodular Cover, and Connected Polymatroid) that strictly generalize Set Cover. We give a (1-γ)ln N-approximation algorithm for these problems that runs in exp(tildeO(Nγ)) time, for any 1/2 ≤ γ < 1.