Fixed-parameter approximation: conceptual framework and approximability results
From MaRDI portal
Publication:2379929
DOI10.1007/s00453-008-9223-xzbMath1186.68557OpenAlexW2157124529MaRDI QIDQ2379929
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
approximation algorithmapproximation schemefixed-parameter tractabilityfixed parameter computationfixed-parameter approximation
Related Items (9)
Backdoors to Satisfaction ⋮ Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ On subexponential and FPT-time inapproximability
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the efficiency of polynomial time approximation schemes
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Optimization, approximation, and complexity classes
- On fixed-parameter tractability and approximability of NP optimization problems
- On limited nondeterminism and the complexity of the V-C dimension
- The inapproximability of non-NP-hard optimization problems.
- On the existence of subexponential parameterized algorithms
- On the structure of parameterized problems in NP
- On Parameterized Approximability
- Parameterized Approximation Problems
- Approximation algorithms for NP-complete problems on planar graphs
- On the Amount of Nondeterminism and the Power of Verifying
- Parameterized complexity: exponential speed-up for planar graph problems
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Mathematical Foundations of Computer Science 2004
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Computing and Combinatorics
- Improved Parameterized Upper Bounds for Vertex Cover
This page was built for publication: Fixed-parameter approximation: conceptual framework and approximability results
