Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATION CLASSES:
Reports tagged with Approximation Classes:
TR03-031 | 8th April 2003
Birgit Schelm

Average-Case Complexity Theory of Approximation Problems

Both average-case complexity and the study of the approximability properties of NP-optimization problems are well established and active fields of research. By applying the notion of average-case complexity to approximation problems we provide a formal framework that allows the classification of NP-optimization problems according to their average-case approximability. Thus, known ... more >>>




ISSN 1433-8092 | Imprint