Treffer: Approximation Classes for Real Number Optimization Problems.

A fundamental research area in relation with analyzing the complexity of optimization problems are approximation algorithms. For combinatorial optimization a vast theory of approximation algorithms has been developed, see [1]. Many natural optimization problems involve real numbers and thus an uncountable search space of feasible solutions. A uniform complexity theory for real number decision problems was introduced by Blum, Shub, and Smale [4]. However, approximation algorithms were not yet formally studied in their model. In this paper we develop a structural theory of optimization problems and approximation algorithms for the BSS model similar to the above mentioned one for combinatorial optimization. We introduce a class $NPO_{\mathbb {R}}$ of real optimization problems closely related to $NP_{\mathbb {R}}$. The class $NPO_{\mathbb {R}}$ has four natural subclasses. For each of those we introduce and study real approximation classes $APX_{\mathbb {R}}$ and $PTAS_{\mathbb {R}}$ together with reducibility and completeness notions. As main results we establish the existence of natural complete problems for all these classes. [ABSTRACT FROM AUTHOR]

Copyright of Unconventional Computation (9783540385936) is the property of Springer eBooks and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)