Tight bounds on subexponential time approximation of set cover and related problems

DOI10.1007/978-3-030-80879-2_11OpenAlexW3183852655MaRDI QIDQ2117696

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

Publication date: 22 March 2022

Full work available at URL: https://arxiv.org/abs/2008.05374

zbMATH Keywords

lower boundsset coversubexponential time algorithms

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sub-constant error probabilistically checkable proof of almost-linear size
• Exponential-time approximation of weighted set cover
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Approximating the weight of shallow Steiner trees
• Which problems have strongly exponential complexity?
• An analysis of the greedy algorithm for the submodular set covering problem
• New tools and connections for exponential-time approximation
• A threshold of ln n for approximating set cover
• Polylogarithmic inapproximability
• A Greedy Heuristic for the Set-Covering Problem
• On the hardness of approximating minimization problems
• Approximation Algorithms for Directed Steiner Problems
• Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
• O (log ² k / log log k )-approximation algorithm for directed Steiner tree
• Analytical approach to parallel repetition
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• The steiner problem in graphs

This page was built for publication: Tight bounds on subexponential time approximation of set cover and related problems