Abstract
We show that SET-COVER on instances with N elements cannot be approximated within (1−𝛾)ln𝑁-factor in time exp(𝑁𝛾−𝛿), for any 00, assuming the Exponential Time Hypothesis. This essentially matches the best upper bound known by Cygan, Kowalik, and Wykurz [6] of (1−𝛾)ln𝑁-factor in time 𝑒𝑥𝑝(𝑂(𝑁𝛾)).
The lower bound is obtained by extracting a standalone reduction from LABEL-COVER to SET-COVER from the work of Moshkovitz [18], 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𝑁-approximation algorithm for these problems that runs in 𝑒𝑥𝑝(𝑂̃ (𝑁𝛾)) time, for any 1/2≤𝛾
The lower bound is obtained by extracting a standalone reduction from LABEL-COVER to SET-COVER from the work of Moshkovitz [18], 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𝑁-approximation algorithm for these problems that runs in 𝑒𝑥𝑝(𝑂̃ (𝑁𝛾)) time, for any 1/2≤𝛾
| Original language | English |
|---|---|
| Title of host publication | Approximation and Online Algorithms |
| Editors | Christos Kaklamanis, Asaf Levin |
| Publisher | Springer, Cham |
| Pages | 159-173 |
| Volume | 12806 |
| ISBN (Electronic) | 978-3-030-80879-2 |
| ISBN (Print) | 978-3-030-80878-5 |
| DOIs | |
| Publication status | Published - 2021 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer Cham |
| Volume | 12806 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Other keywords
- Subexponential time algorithms
- Lower bounds
- Set cover