Exponential-time approximation of weighted set cover
From MaRDI portal
Publication:989538
DOI10.1016/j.ipl.2009.05.003zbMath1202.68482OpenAlexW1985694287MaRDI QIDQ989538
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
Related Items (24)
An exact algorithm to extend lifetime through roles allocation in sensor networks with connectivity constraints ⋮ Time-approximation trade-offs for inapproximable problems ⋮ The Parameterized Complexity of the Rainbow Subgraph Problem ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Exponential approximation schemata for some network design problems ⋮ Parameterized approximation via fidelity preserving transformations ⋮ 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 ⋮ Improved approximation bounds for the minimum rainbow subgraph problem ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ 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 ⋮ In)approximability of Maximum Minimal FVS ⋮ Algorithms for dominating clique problems ⋮ New tools and connections for exponential-time approximation ⋮ Lift-and-project methods for set cover and knapsack ⋮ (In)approximability of maximum minimal FVS ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ An Exponential Time 2-Approximation Algorithm for Bandwidth ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ Tight bounds on subexponential time approximation of set cover and related problems
Cites Work
- Unnamed Item
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Zero knowledge and the chromatic number
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- 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
- Confronting hardness using a hybrid approach
- Measure and conquer
- 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
This page was built for publication: Exponential-time approximation of weighted set cover
