Efficient approximation of Min Set Cover by moderately exponential algorithms
From MaRDI portal
Publication:1019736
DOI10.1016/j.tcs.2009.02.007zbMath1166.68043OpenAlexW2009411756MaRDI QIDQ1019736
Bruno Escoffier, Vangelis Th. Paschos, Nicolas Bourgeois
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
Related Items (14)
Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms ⋮ Time-approximation trade-offs for inapproximable problems ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Exponential approximation schemata for some network design problems ⋮ Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ When polynomial approximation meets exact computation ⋮ Approximating MAX SAT by moderately exponential and parameterized algorithms ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ When polynomial approximation meets exact computation ⋮ Algorithms for dominating clique problems ⋮ Approximation of min coloring by moderately exponential algorithms ⋮ Exponential-time approximation of weighted set cover ⋮ Moderately exponential time and fixed parameter approximation algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- Non deterministic polynomial optimization problems and their approximations
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Differential approximation algorithms for some combinatorial optimization problems
- A modified greedy heuristic for the set covering problem with improved worst case bound
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- On the differential approximation of MIN SET COVER
- A note on the complexity of minimum dominating set
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- z-Approximations
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On Parameterized Approximability
- Parameterized Approximation Problems
- Set Partitioning via Inclusion-Exclusion
- Confronting hardness using a hybrid approach
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- 3-coloring in time
- STACS 2005
This page was built for publication: Efficient approximation of Min Set Cover by moderately exponential algorithms
