Moderately exponential time and fixed parameter approximation algorithms
DOI10.1080/02331934.2012.704515zbMath1310.68239MaRDI QIDQ2868915
Bruno Escoffier, Emeric Tourniaire, Vangelis Th. Paschos
Publication date: 19 December 2013
Published in: Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/02331934.2012.704515
polynomial approximation; combinatorial problem; fixed parameter tractability; NP-hard problem; exact computation; moderately exponential approximation
68Q25: Analysis of algorithms and problem complexity
90C27: Combinatorial optimization
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- Exact exponential algorithms.
- Approximating the minimum maximal independence number
- Enumerating maximal independent sets with applications to graph colouring.
- Exact and approximate bandwidth
- Improved approximation algorithms for maximum graph partitioning problems
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- Computing small partial coverings
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- The Steiner problem with edge lengths 1 and 2
- Optimization, approximation, and complexity classes
- Worst-case study of local search for MAX-\(k\)-SAT.
- Approximating the bandwidth via volume respecting embeddings
- Which problems have strongly exponential complexity?
- Improved exact algorithms for MAX-SAT
- Fast algorithms for max independent set
- The parameterized approximability of TSP with deadlines
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Vertex Cover: Further Observations and Further Improvements
- Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
- 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
- An Exponential Time 2-Approximation Algorithm for Bandwidth
- Vertex packings: Structural properties and algorithms
- Improved Upper Bounds for Partial Vertex Cover
- Some optimal inapproximability results
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- The PCP theorem by gap amplification
- MAX SAT approximation beyond the limits of polynomial-time approximation
