Polynomial time approximation schemes and parameterized complexity
From MaRDI portal
Publication:867860
DOI10.1016/j.dam.2006.04.040zbMath1109.68135MaRDI QIDQ867860
Ge Xia, Iyad A. Kanj, Xiuzhen Huang, Jian'er Chen
Publication date: 19 February 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.040
approximation algorithm; parameterized complexity; polynomial time approximation scheme; W-hierarchy
68W25: Approximation algorithms
Related Items
Structure of polynomial-time approximation, A problem reduction based approach to discrete optimization algorithm design, Safe Approximation and Its Relation to Kernelization, Parameterized Complexity and Subexponential-Time Computability
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the efficiency of polynomial time approximation schemes
- Toward a unified approach for the classification of NP-complete optimization problems
- Non deterministic polynomial optimization problems and their approximations
- Characterizing parallel hierarchies by reducibilities
- Optimization, approximation, and complexity classes
- On fixed-parameter tractability and approximability of NP optimization problems
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Deciding first-order properties of locally tree-decomposable structures
- Algorithms for Scheduling Independent Tasks
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- On Syntactic versus Computational Views of Approximability
- Approximation algorithms for NP-complete problems on planar graphs
