Moderately exponential time and fixed parameter approximation algorithms
combinatorial problemexact computationfixed parameter tractabilitymoderately exponential approximationNP-hard problempolynomial approximation
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- Preface
- Moderately exponential approximation
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- A threshold of ln n for approximating set cover
- An exponential time 2-approximation algorithm for bandwidth
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- Approximating the bandwidth via volume respecting embeddings
- Approximating the minimum maximal independence number
- Approximation algorithms for maximization problems arising in graph partitioning
- Approximation of min coloring by moderately exponential algorithms
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Computing small partial coverings
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Enumerating maximal independent sets with applications to graph colouring.
- Exact and approximate bandwidth
- Exact exponential algorithms.
- Exponential-time approximation of weighted set cover
- Fast algorithms for max independent set
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1839431 (Why is no real title available?)
- Improved approximation algorithms for maximum graph partitioning problems
- Improved exact algorithms for MAX-SAT
- Improved Upper Bounds for Partial Vertex Cover
- MAX SAT approximation beyond the limits of polynomial-time approximation
- On Parameterized Approximability
- Optimization, approximation, and complexity classes
- Parameterized Approximation Problems
- Proof verification and the hardness of approximation problems
- Set partitioning via inclusion-exclusion
- Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
- Some optimal inapproximability results
- The parameterized approximability of TSP with deadlines
- The PCP theorem by gap amplification
- The Steiner problem with edge lengths 1 and 2
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
- Which problems have strongly exponential complexity?
- Worst-case study of local search for MAX-\(k\)-SAT.
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- Super-polynomial approximation branching algorithms
- Moderately exponential approximation
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Exponential approximation schemata for some network design problems
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- Preface
This page was built for publication: Moderately exponential time and fixed parameter approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2868915)
