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

efficient computationEPTASNP-optimization problemsapproximation-preserving reductionsasymptotic polynomial-time approximation schemespolynomial-time approximation schemesstructure of complexity classes

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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 THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
• On Approximate Solutions for Combinatorial Optimization Problems
• On Syntactic versus Computational Views of Approximability
• On approximation scheme preserving reducibility and its applications
• On fixed-parameter tractability and approximability of NP optimization problems
• 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
• `` Strong NP-Completeness Results

Cited in

(7)

• Polynomial time approximation schemes and parameterized complexity
• The complexity of polynomial-time approximation
• Structures computable in polynomial time. I
• On the efficiency of polynomial time approximation schemes
• 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)?

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)