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
- 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
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- 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
(33)- Efficient approximation of Min Set Cover by moderately exponential algorithms
- An exact algorithm to extend lifetime through roles allocation in sensor networks with connectivity constraints
- Time-approximation trade-offs for inapproximable problems
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Parameterized approximation via fidelity preserving transformations
- Algorithms for dominating clique problems
- Lift-and-project methods for set cover and knapsack
- Improved approximation bounds for the minimum rainbow subgraph problem
- Capacitated domination faster than O(2ⁿ)
- (In)approximability of maximum minimal FVS
- Tight bounds on subexponential time approximation of set cover and related problems
- New tools and connections for exponential-time approximation
- Moderately exponential time and fixed parameter approximation algorithms
- The parameterized complexity of the rainbow subgraph problem
- Exponential Time Complexity of Weighted Counting of Independent Sets
- An exponential time 2-approximation algorithm for bandwidth
- 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
- scientific article; zbMATH DE number 6815827 (Why is no real title available?)
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- Time-approximation trade-offs for inapproximable problems
- Finding large set covers faster via the representation method
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
- A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
- When polynomial approximation meets exact computation
- When polynomial approximation meets exact computation
- In)approximability of Maximum Minimal FVS
- Sidestepping barriers for dominating set in parameterized complexity
- Approximate monotone local search for weighted problems
- Faster exponential-time approximation algorithms using approximate monotone local search
- Approximate monotone local search for weighted problems
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)
