Structure in Approximation Classes
Copyright policy )Structure in Approximation Classes
Summary: The study of the approximability properties of NP-hard optimization problems has recently made great advances mainly due to the results obtained in the field of proof checking. The last important breakthrough proves the APX-completeness of several important optimization problems and thus reconciles ``two distinct views of approximation classes: syntactic and computational'' [\textit{S. Khanna} et al., in: Proc. 35th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 819-830 (1994)]. In this paper we obtain new results on the structure of several computationally defined approximation classes. In particular, after defining a new approximation preserving reducibility to be used for as many approximation classes as possible, we give the first examples of natural NPO-complete problems and the first examples of natural APX-intermediate problems. Moreover, we state new connections between the approximability properties and the query complexity of NPO problems.
- Sapienza University of Rome Italy
- Roma Tre University Italy
- Royal Institute of Technology Sweden
- University of Florence Italy
APX-intermediate problems, approximation classes, Approximation algorithms, reducibilities, complexity classes, NPO-complete problems, complexity classes, reducibilities, approximation algorithms, Algorithms, Computation theory, Functions, Optimization, Polynomials, Complexity classes (hierarchies, relations among complexity classes, etc.), Other degrees and reducibilities in computability and recursion theory, approximation algorithms
APX-intermediate problems, approximation classes, Approximation algorithms, reducibilities, complexity classes, NPO-complete problems, complexity classes, reducibilities, approximation algorithms, Algorithms, Computation theory, Functions, Optimization, Polynomials, Complexity classes (hierarchies, relations among complexity classes, etc.), Other degrees and reducibilities in computability and recursion theory, approximation algorithms
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).31 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!