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

Magnús M. Halldórsson, Guy Kortsarz, Marek Cygan

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review


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≤𝛾
Original languageEnglish
Title of host publicationApproximation and Online Algorithms
EditorsChristos Kaklamanis, Asaf Levin
PublisherSpringer, Cham
ISBN (Electronic)978-3-030-80879-2
ISBN (Print)978-3-030-80878-5
Publication statusPublished - 2021

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other keywords

  • Subexponential time algorithms
  • Lower bounds
  • Set cover


Dive into the research topics of 'Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems'. Together they form a unique fingerprint.

Cite this