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

DOI10.1007/978-3-030-80879-2_11MaRDI QIDQ2117696zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• On approximation of the submodular set cover problem
• Set cover in sub-linear time
• Subexponential algorithms for partial cover problems
• Subexponential algorithms for partial cover problems
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Exponential-time approximation of weighted set cover
• Partial sublinear time approximation and inapproximation for maximum coverage
• Tight bounds for single-pass streaming complexity of the set cover problem
• Tight bounds for single-pass streaming complexity of the set cover problem
• Tight approximation bounds for combinatorial frugal coverage algorithms

Cites work

• O(^2 k/ k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm
• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• An analysis of the greedy algorithm for the submodular set covering problem
• Analytical approach to parallel repetition
• Approximating the weight of shallow Steiner trees
• Approximation algorithms for combinatorial problems
• Approximation Algorithms for Directed Steiner Problems
• Exponential-time approximation of weighted set cover
• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• scientific article; zbMATH DE number 1256762 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• New tools and connections for exponential-time approximation
• On the hardness of approximating minimization problems
• On the ratio of optimal integral and fractional covers
• Polylogarithmic inapproximability
• Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
• Sub-constant error probabilistically checkable proof of almost-linear size
• The steiner problem in graphs
• Which problems have strongly exponential complexity?

Cited in

(4)

• Efficient approximation of Min Set Cover by moderately exponential algorithms
• \(O(n \log n)\) procedures for tightening cover inequalities
• Tight approximation bounds for combinatorial frugal coverage algorithms
• A Tight Bound for Stochastic Submodular Cover

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117696)