Efficient approximation of Min Set Cover by moderately exponential algorithms
From MaRDI portal
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
- scientific article; zbMATH DE number 5605070 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- 3-coloring in time
- A Greedy Heuristic for the Set-Covering Problem
- A modified greedy heuristic for the set covering problem with improved worst case bound
- A note on the complexity of minimum dominating set
- A threshold of ln n for approximating set cover
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithms for combinatorial problems
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- Confronting hardness using a hybrid approach
- Design by measure and conquer. A faster exact algorithm for dominating set
- Differential approximation algorithms for some combinatorial optimization problems
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Non deterministic polynomial optimization problems and their approximations
- On Parameterized Approximability
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- On the differential approximation of MIN SET COVER
- On the ratio of optimal integral and fractional covers
- Parameterized Approximation Problems
- Proof verification and the hardness of approximation problems
- STACS 2005
- Set partitioning via inclusion-exclusion
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- \(z\)-approximations
Cited in
(19)- Tight bounds on subexponential time approximation of set cover and related problems
- Moderately exponential time and fixed parameter approximation algorithms
- An exponential time 2-approximation algorithm for bandwidth
- When polynomial approximation meets exact computation
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- Exponential approximation schemata for some network design problems
- A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- Improved approximation algorithms for low-density instances of the minimum entropy set cover problem
- Algorithms for dominating clique problems
- Time-approximation trade-offs for inapproximable problems
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- scientific article; zbMATH DE number 1947050 (Why is no real title available?)
- scientific article; zbMATH DE number 784428 (Why is no real title available?)
- When polynomial approximation meets exact computation
- Approximating MAX SAT by moderately exponential and parameterized 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)
