AVERAGE MEASURE, DESCRIPTIVE COMPLEXITY AND APPROXIMATION OF MAXIMIZATION PROBLEMS

DOI10.1142/S0129054193000031zbMath0783.68044MaRDI QIDQ4275181

Pierluigi Crescenzi, Riccardo Silvestri

Publication date: 26 January 1994

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

zbMATH Keywords

approximation algorithmsdescriptive complexitymaximization problemsguaranteed average measure

Mathematics Subject Classification ID

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

Related Items

Approximate solution of NP optimization problems