Structure of polynomial-time approximation
DOI10.1007/s00224-011-9366-zzbMath1288.68083OpenAlexW1971077453MaRDI QIDQ692893
Erik Jan van Leeuwen, Jan van Leeuwen
Publication date: 6 December 2012
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-011-9366-z
NP-optimization problemsefficient computationEPTASapproximation-preserving reductionsasymptotic polynomial-time approximation schemespolynomial-time approximation schemesstructure of complexity classes
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the efficiency of polynomial time approximation schemes
- There is no asymptotic PTAS for two-dimensional vector packing
- Completeness in approximation classes
- Polynomial time approximation schemes and parameterized complexity
- Approximation algorithms for extensible bin packing
- Non deterministic polynomial optimization problems and their approximations
- Optimization, approximation, and complexity classes
- The hardness of approximation: Gap location
- Logical definability of NP optimization problems
- On fixed-parameter tractability and approximability of NP optimization problems
- On the existence of subexponential parameterized algorithms
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Approximation properties of NP minimization classes
- On approximation scheme preserving reducibility and its applications
- The complexity of polynomial-time approximation
- Proof verification and the hardness of approximation problems
- On Approximate Solutions for Combinatorial Optimization Problems
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Bounds for Assembly Line Balancing Heuristics
- ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
- `` Strong NP-Completeness Results
- On Syntactic versus Computational Views of Approximability
- Structure in Approximation Classes
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Mathematical Foundations of Computer Science 2004
- Algorithm Theory - SWAT 2004
- Better Approximation Schemes for Disk Graphs
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Structure of polynomial-time approximation
