Structure of polynomial-time approximation

DOI10.1007/S00224-011-9366-ZMaRDI QIDQ692893zbMATH OpenOpenAlexFDO

Authors Erik Jan van Leeuwen, J. Van Leeuwen

Publication date 6 December 2012

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00224-011-9366-z

zbMATH Keywords

approximation-preserving reductionsasymptotic polynomial-time approximation schemesefficient computationEPTASNP-optimization problemspolynomial-time approximation schemesstructure of complexity classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• On the efficiency of polynomial time approximation schemes
• The complexity of polynomial-time approximation
• Polynomial time approximation schemes and parameterized complexity
• Mathematical Foundations of Computer Science 2004
• On approximation scheme preserving reducibility and its applications

Cites work

• `` Strong NP-Completeness Results
• Algorithm Theory - SWAT 2004
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Approximation algorithms for extensible bin packing
• Approximation properties of NP minimization classes
• Better Approximation Schemes for Disk Graphs
• Bounds for Assembly Line Balancing Heuristics
• Completeness in approximation classes
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 3750313 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Logical definability of NP optimization problems
• Mathematical Foundations of Computer Science 2004
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Non deterministic polynomial optimization problems and their approximations
• On Approximate Solutions for Combinatorial Optimization Problems
• On approximation scheme preserving reducibility and its applications
• On fixed-parameter tractability and approximability of NP optimization problems
• On Syntactic versus Computational Views of Approximability
• ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
• On the efficiency of polynomial time approximation schemes
• On the existence of subexponential parameterized algorithms
• Optimization, approximation, and complexity classes
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Polynomial time approximation schemes and parameterized complexity
• Proof verification and the hardness of approximation problems
• Structure in Approximation Classes
• The complexity of polynomial-time approximation
• The hardness of approximation: Gap location
• There is no asymptotic PTAS for two-dimensional vector packing

Cited in

(10)

• Structures computable in polynomial time. I
• The complexity of polynomial-time approximation
• On the efficiency of polynomial time approximation schemes
• scientific article; zbMATH DE number 1256750 (Why is no real title available?)
• scientific article; zbMATH DE number 1305477 (Why is no real title available?)
• scientific article; zbMATH DE number 1086675 (Why is no real title available?)
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Shortcutting directed and undirected networks with a degree constraint
• Mathematical Foundations of Computer Science 2004
• 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)