Polynomial time approximation schemes and parameterized complexity

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

zbMATH Keywords

approximation algorithmparameterized complexitypolynomial time approximation schemeW-hierarchy

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items (7)

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

This page was built for publication: Polynomial time approximation schemes and parameterized complexity