Polynomial time approximation schemes and parameterized complexity
From MaRDI portal
Publication:867860
DOI10.1016/j.dam.2006.04.040zbMath1109.68135OpenAlexW2007441033MaRDI QIDQ867860
Iyad A. Kanj, Xiuzhen Huang, Ge Xia, 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
Related Items
Safe Approximation and Its Relation to Kernelization ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Knapsack problems: a parameterized point of view ⋮ Scheduling two-stage jobs on multiple flowshops ⋮ Structure of polynomial-time approximation ⋮ A problem reduction based approach to discrete optimization algorithm design
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
