scientific article; zbMATH DE number 17535

MaRDI QIDQ3974859zbMATH OpenFDO

Authors Pilu Crescenzi

Publication date 26 June 1992

zbMATH Keywords

fully polynomial-time approximation schemepolynomial approximation scheme\(NP\) optimization problemsAPX-problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Completeness in approximation classes
• Structure in Approximation Classes
• Optimization, approximation, and complexity classes
• scientific article; zbMATH DE number 847149
• Completeness in approximation classes beyond APX

Cited in

(18)

• scientific article; zbMATH DE number 1893715 (Why is no real title available?)
• scientific article; zbMATH DE number 5033149 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2003
• scientific article; zbMATH DE number 5263318 (Why is no real title available?)
• COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
• Approximation preserving reductions
• Bounds on Quasi-Completeness
• scientific article; zbMATH DE number 4114002 (Why is no real title available?)
• Completion by perturbations
• scientific article; zbMATH DE number 4155879 (Why is no real title available?)
• Approximating values and solutions of NP-optimization problems: concepts and examples
• On the approximability of the maximum common subgraph problem
• scientific article; zbMATH DE number 88935 (Why is no real title available?)
• Classes bounded by incomplete sets
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Approximation of coNP sets by NP-complete sets
• A survey on the structure of approximation classes
• On approximation scheme preserving reducibility and its applications

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3974859)