Structure of polynomial-time approximation
DOI10.1007/S00224-011-9366-ZzbMATH Open1288.68083OpenAlexW1971077453MaRDI QIDQ692893FDOQ692893
Erik Jan van Leeuwen, J. 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
Recommendations
efficient computationEPTASNP-optimization problemsapproximation-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)
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- The hardness of approximation: Gap location
- Proof verification and the hardness of approximation problems
- Title not available (Why is that?)
- Structure in Approximation Classes
- `` Strong NP-Completeness Results
- On the existence of subexponential parameterized algorithms
- On the efficiency of polynomial time approximation schemes
- There is no asymptotic PTAS for two-dimensional vector packing
- Completeness in approximation classes
- Bounds for Assembly Line Balancing Heuristics
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Mathematical Foundations of Computer Science 2004
- Polynomial time approximation schemes and parameterized complexity
- On Syntactic versus Computational Views of Approximability
- Algorithm Theory - SWAT 2004
- Non deterministic polynomial optimization problems and their approximations
- Better Approximation Schemes for Disk Graphs
- Graph-Theoretic Concepts in Computer Science
- On Approximate Solutions for Combinatorial Optimization Problems
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Logical definability of NP optimization problems
- Approximation properties of NP minimization classes
- On approximation scheme preserving reducibility and its applications
- The complexity of polynomial-time approximation
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Title not available (Why is that?)
- On fixed-parameter tractability and approximability of NP optimization problems
- ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
- Approximation algorithms for extensible bin packing
Cited In (6)
- The complexity of polynomial-time approximation
- Structures computable in polynomial time. I
- Mathematical Foundations of Computer Science 2004
- Shortcutting directed and undirected networks with a degree constraint
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- Polynomial time approximation schemes and parameterized complexity
This page was built for publication: Structure of polynomial-time approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692893)
