ECCC-Report TR03-031https://eccc.weizmann.ac.il/report/2003/031Comments and Revisions published for TR03-031en-usThu, 24 Apr 2003 10:32:07 +0300
Paper TR03-031
| Average-Case Complexity Theory of Approximation Problems |
Birgit Schelm
https://eccc.weizmann.ac.il/report/2003/031Both 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 results about the average-case behaviour of approximation algorithms -- with respect to their running time as well as their performance ratio -- can be unified, though subsuming results about problems being approximable within a certain factor with high probability under the new classes is not straightforward. The structural properties of this framework provide an interesting field of study on their own. We not only define appropriate average-case approximation classes, but also a reduction that preserves approximability within average polynomial time. We show that the class of NP-optimization problems with P-computable input distributions has complete problems with respect to this reduction. The inclusion structure of the average-case approximation classes is investigated. E.g. using a new result by Buhrman, Fortnow and Pavan we are able to show that DistNPO \subseteq Avg_t-PTAS if DistNP \subseteq AvgP.
Thu, 24 Apr 2003 10:32:07 +0300https://eccc.weizmann.ac.il/report/2003/031