Exponential-time approximation of weighted set cover
From MaRDI portal
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
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- 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}\)
- Confronting hardness using a hybrid approach
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
- Expected Computation Time for Hamiltonian Path problem
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Improved Parameterized Upper Bounds for Vertex Cover
- MAX SAT approximation beyond the limits of polynomial-time approximation
- Measure and conquer
- Zero knowledge and the chromatic number
Cited in
(29)- Tight bounds on subexponential time approximation of set cover and related problems
- scientific article; zbMATH DE number 6815827 (Why is no real title available?)
- Moderately exponential time and fixed parameter approximation algorithms
- Capacitated domination faster than \(O(2^n)\)
- An exponential time 2-approximation algorithm for bandwidth
- An exponential time 2-approximation algorithm for bandwidth
- When polynomial approximation meets exact computation
- New tools and connections for exponential-time approximation
- Improved approximation bounds for the minimum rainbow subgraph problem
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Exponential Time Complexity of Weighted Counting of Independent Sets
- Parameterized approximation via fidelity preserving transformations
- (In)approximability of maximum minimal FVS
- Time-approximation trade-offs for inapproximable problems
- Exponential approximation schemata for some network design problems
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- In)approximability of Maximum Minimal FVS
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Algorithms for dominating clique problems
- An exact algorithm to extend lifetime through roles allocation in sensor networks with connectivity constraints
- Time-approximation trade-offs for inapproximable problems
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- Lift-and-project methods for set cover and knapsack
- When polynomial approximation meets exact computation
- Finding large set covers faster via the representation method
- The parameterized complexity of the rainbow subgraph problem
- A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
- Approximating MAX SAT by moderately exponential and parameterized 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)
