scientific article; zbMATH DE number 17535

zbMATH Open0756.68038MaRDI QIDQ3974859FDOQ3974859

Authors: Pilu Crescenzi 

Publication date: 26 June 1992

Title of this publication is not available (Why is that?)

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

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)

Cited In (18)

• Classes bounded by incomplete sets
• Approximating values and solutions of NP-optimization problems: concepts and examples
• Mathematical Foundations of Computer Science 2003
• On the approximability of the maximum common subgraph problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• A survey on the structure of approximation classes
• Title not available (Why is that?)
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Title not available (Why is that?)
• COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
• Bounds on Quasi-Completeness
• Approximation of coNP sets by NP-complete sets
• Completion by perturbations
• Approximation preserving reductions
• On approximation scheme preserving reducibility and its applications
• Title not available (Why is that?)
• Title not available (Why is that?)

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)