Fixed-parameter approximation: conceptual framework and approximability results
From MaRDI portal
Publication:2379929
DOI10.1007/S00453-008-9223-XzbMATH Open1186.68557OpenAlexW2157124529MaRDI QIDQ2379929FDOQ2379929
Authors: Xiuzhen Huang, Liming Cai 
Publication date: 23 March 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9223-x
Recommendations
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On fixed-parameter tractability and approximability of NP optimization problems
- Mathematical Foundations of Computer Science 2004
- On Parameterized Approximability
- Polynomial time approximation schemes and parameterized complexity
approximation algorithmfixed-parameter tractabilityapproximation schemefixed parameter computationfixed-parameter approximation
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Parameterized Approximation Problems
- Title not available (Why is that?)
- Approximation algorithms for NP-complete problems on planar graphs
- Title not available (Why is that?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- On the structure of parameterized problems in NP
- On the existence of subexponential parameterized algorithms
- On the efficiency of polynomial time approximation schemes
- On limited nondeterminism and the complexity of the V-C dimension
- Improved Parameterized Upper Bounds for Vertex Cover
- Mathematical Foundations of Computer Science 2004
- On Parameterized Approximability
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Parameterized complexity: exponential speed-up for planar graph problems
- On the Amount of Nondeterminism and the Power of Verifying
- On fixed-parameter tractability and approximability of NP optimization problems
- Title not available (Why is that?)
- The inapproximability of non-NP-hard optimization problems.
- Computing and Combinatorics
Cited In (14)
- An exponential time 2-approximation algorithm for bandwidth
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Polynomial kernelizations for \(\text{MIN} \text{F}^+ \Pi_1\) and \(\text{MAX NP}\)
- Backdoors to satisfaction
- Improved approximations for hard optimization problems via problem instance classification
- Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
- Data reductions and combinatorial bounds for improved approximation algorithms
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- The constant inapproximability of the parameterized dominating set problem
- Parameterized approximation via fidelity preserving transformations
- Parameterized Approximation Problems
- On subexponential and FPT-time inapproximability
- Fixed-Parameter and Approximation Algorithms: A New Look
This page was built for publication: Fixed-parameter approximation: conceptual framework and approximability results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379929)
