Structure in approximation classes

被引：29

作者：

Crescenzi, P ^{[1
]}

Kann, V

Silvestri, R

Trevisan, L

机构：

[1] Univ Florence, Dipartimento Sistemi & Informat, I-50134 Florence, Italy

[2] Royal Inst Technol, Dept Numer Anal & Comp Sci, S-10044 Stockholm, Sweden

[3] Univ Roma La Sapienza, Dipartimento Sci Informaz, I-00198 Rome, Italy

[4] MIT, Comp Sci Lab, Cambridge, MA 02139 USA

来源：

SIAM JOURNAL ON COMPUTING | 1999年 / 28卷 / 05期

关键词：

complexity classes; reducibilities; approximation algorithms;

D O I：

10.1137/S0097539796304220

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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" [S. Khanna et al., in Proc. 35th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 819-830]. 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.

引用

页码：1759 / 1782

页数：24

共 44 条

[21]

Impagliazzo R., 1988, Proceedings: Structure in Complexity Theory Third Annual Conference (Cat. No.88CH2542-9), P29, DOI 10.1109/SCT.1988.5260

[22] APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS [J].