Back to Search Start Over

Average-Case Non-Approximability of Optimisation Problems.

Authors :
Schelm, Birgit
Source :
Theory of Computing Systems. Aug2007, Vol. 41 Issue 2, p351-368. 18p. 1 Diagram.
Publication Year :
2007

Abstract

Both average-case complexity and the study of the approximability of NP optimisation problems are well established and active fields of research. Many results concerning the average behaviour of approximation algorithms for NP 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: 1. The class of NP optimisation problems with p-computable input distributions has complete problems with respect to an average-approximability preserving reduction. 2. The average-time variants of worst-case approximation classes form a strict hierarchy if NP is not easy on average. By linking average-ratio approximation algorithms to polynomial-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 NP-problems with p-computable input distributions have polynomial-time algorithm schemes. 3. The question whether NP is easy on average is equivalent to the question whether every NP optimisation problem with a p-computable input distribution has an average polynomial-time approximation scheme. An extended abstract of this paper appeared in [28]. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
14324350
Volume :
41
Issue :
2
Database :
Academic Search Index
Journal :
Theory of Computing Systems
Publication Type :
Academic Journal
Accession number :
25811423
Full Text :
https://doi.org/10.1007/s00224-007-2012-0