×

zbMATH — the first resource for mathematics

Relations between average case complexity and approximation complexity. (English) Zbl 1192.68358
Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press (ISBN 1-581-13495-9). 534-543, electronic only (2002).
For the entire collection see [Zbl 1074.68502].

MSC:
68Q25 Analysis of algorithms and problem complexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI