Efficient approximation of Min Set Cover by moderately exponential algorithms
From MaRDI portal
Publication:1019736
DOI10.1016/J.TCS.2009.02.007zbMATH Open1166.68043OpenAlexW2009411756MaRDI QIDQ1019736FDOQ1019736
Authors: Bruno Escoffier, Nicolas Bourgeois, Vangelis Th. Paschos 
Publication date: 28 May 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2098
Recommendations
- scientific article; zbMATH DE number 1947050
- scientific article; zbMATH DE number 784428
- A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Approximating min sum set cover
- Exponential-time approximation of weighted set cover
- Tight bounds on subexponential time approximation of set cover and related problems
- On the differential approximation of MIN SET COVER
- Algorithms – ESA 2005
- A constant factor approximation algorithm for generalized MIN-sum set cover
Cites Work
- A threshold of ln n for approximating set cover
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the ratio of optimal integral and fractional covers
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Proof verification and the hardness of approximation problems
- Parameterized Approximation Problems
- Title not available (Why is that?)
- 3-coloring in time
- Differential approximation algorithms for some combinatorial optimization problems
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- \(z\)-approximations
- Confronting hardness using a hybrid approach
- Set partitioning via inclusion-exclusion
- Non deterministic polynomial optimization problems and their approximations
- On Parameterized Approximability
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- A note on the complexity of minimum dominating set
- Title not available (Why is that?)
- Design by measure and conquer. A faster exact algorithm for dominating set
- STACS 2005
- On the differential approximation of MIN SET COVER
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- A modified greedy heuristic for the set covering problem with improved worst case bound
Cited In (19)
- An exponential time 2-approximation algorithm for bandwidth
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Exponential approximation schemata for some network design problems
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- Improved approximation algorithms for low-density instances of the minimum entropy set cover problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Algorithms for dominating clique problems
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Time-approximation trade-offs for inapproximable problems
- When polynomial approximation meets exact computation
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- Tight bounds on subexponential time approximation of set cover and related problems
- When polynomial approximation meets exact computation
- Moderately exponential time and fixed parameter approximation algorithms
This page was built for publication: Efficient approximation of Min Set Cover by moderately exponential algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1019736)
