Treffer: Average-Case Non-approximability of Optimisation Problems.

Both average-case complexity and the study of the approximability of optimisation problems are well established and active fields of research. Many results concerning the average behaviour of approximation algorithms for optimisation problems exist, both with respect to their running time and their performance ratio, but a theoretical framework to examine their structural properties with respect to their average-case approximability is not yet established. With this paper, we hope to fill the gap and provide not only the necessary definitions, but show that 1The class of optimisation problems with p-computable input distributions has complete problems with respect to an average-approximability preserving reduction. 2The average-time variants of worst-case approximation classes form a strict hierarchy if is not easy on average. By linking average-ratio approximation algorithms to p-time algorithms schemes, we can prove similar hierarchy results for the average-ratio versions of the approximation classes. This is done under the premise that not all -problems with p-computable input distributions have p-time algorithm schemes. 3The question whether is easy on average is equivalent to the question whether every optimisation problem with a p-computable input distribution has an average p-time approximation scheme. Classification: Computational and structural complexity. [ABSTRACT FROM AUTHOR]