AVERAGE MEASURE, DESCRIPTIVE COMPLEXITY AND APPROXIMATION OF MAXIMIZATION PROBLEMS

DOI10.1142/S0129054193000031MaRDI QIDQ4275181zbMATH OpenFDO

Authors Pilu Crescenzi, Riccardo Silvestri

Publication date 26 January 1994

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054193000031

zbMATH Keywords

approximation algorithmsdescriptive complexityguaranteed average measuremaximization problems

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 515727
• scientific article; zbMATH DE number 1559517
• Quantifiers and approximation
• Completeness in approximation classes
• A note on the descriptive complexity of maximization problems

Cited in

(1)

• Approximate solution of NP optimization problems

This page was built for publication: AVERAGE MEASURE, DESCRIPTIVE COMPLEXITY AND APPROXIMATION OF MAXIMIZATION PROBLEMS

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