Moderately exponential time and fixed parameter approximation algorithms
Publication:2868915
DOI10.1080/02331934.2012.704515zbMath1310.68239OpenAlexW2019648557MaRDI 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 approximationcombinatorial problemfixed parameter tractabilityNP-hard problemexact computationmoderately exponential approximation
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
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
