Exponential-time approximation of weighted set cover
From MaRDI portal
Publication:989538
DOI10.1016/J.IPL.2009.05.003zbMATH Open1202.68482OpenAlexW1985694287MaRDI QIDQ989538FDOQ989538
Authors: Marek Cygan, Łukasz Kowalik, Mateusz Wykurz 
Publication date: 20 August 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.05.003
Recommendations
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- A threshold of ln n for approximating set cover
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Time-approximation trade-offs for inapproximable problems
Cites Work
- A threshold of ln n for approximating set cover
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Confronting hardness using a hybrid approach
- Title not available (Why is that?)
- Improved Parameterized Upper Bounds for Vertex Cover
- Zero knowledge and the chromatic number
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Measure and conquer
- MAX SAT approximation beyond the limits of polynomial-time approximation
- Expected Computation Time for Hamiltonian Path problem
- Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
Cited In (29)
- An exponential time 2-approximation algorithm for bandwidth
- An exponential time 2-approximation algorithm for bandwidth
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
- Exponential approximation schemata for some network design problems
- The parameterized complexity of the rainbow subgraph problem
- Improved approximation bounds for the minimum rainbow subgraph problem
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Title not available (Why is that?)
- Time-approximation trade-offs for inapproximable problems
- Capacitated domination faster than \(O(2^n)\)
- Algorithms for dominating clique problems
- In)approximability of Maximum Minimal FVS
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- Finding large set covers faster via the representation method
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- (In)approximability of maximum minimal FVS
- An exact algorithm to extend lifetime through roles allocation in sensor networks with connectivity constraints
- Time-approximation trade-offs for inapproximable problems
- Lift-and-project methods for set cover and knapsack
- When polynomial approximation meets exact computation
- New tools and connections for exponential-time approximation
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Exponential Time Complexity of Weighted Counting of Independent Sets
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- Tight bounds on subexponential time approximation of set cover and related problems
- Parameterized approximation via fidelity preserving transformations
- When polynomial approximation meets exact computation
- Moderately exponential time and fixed parameter approximation algorithms
This page was built for publication: Exponential-time approximation of weighted set cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989538)
