This paper presents the main results obtained in the field of approximation algorithms in a unified framework. Most of these results have been revisited in order to emphasize two basic tools useful for characterizing approximation classes, that is, combinatorial properties of problems and approximation preserving reducibilities. In particular, after reviewing the most important combinatorial characterizations of the classes PTAS and FPTAS, we concentrate on the class APX and, as a concluding result, we show that this class coincides with the class of optimization problems which are reducible to the maximum satisfiability problem with respect to a polynomial-time approximation preserving reducibility.

APPROXIMATE SOLUTION OF NP OPTIMIZATION PROBLEMS / G. AUSIELLO; P. CRESCENZI; M. PROTASI. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 150:(1995), pp. 1-55. [10.1016/0304-3975(94)00291-P]

APPROXIMATE SOLUTION OF NP OPTIMIZATION PROBLEMS

CRESCENZI, PIERLUIGI;
1995

Abstract

This paper presents the main results obtained in the field of approximation algorithms in a unified framework. Most of these results have been revisited in order to emphasize two basic tools useful for characterizing approximation classes, that is, combinatorial properties of problems and approximation preserving reducibilities. In particular, after reviewing the most important combinatorial characterizations of the classes PTAS and FPTAS, we concentrate on the class APX and, as a concluding result, we show that this class coincides with the class of optimization problems which are reducible to the maximum satisfiability problem with respect to a polynomial-time approximation preserving reducibility.
1995
150
1
55
G. AUSIELLO; P. CRESCENZI; M. PROTASI
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/205999
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 73
  • ???jsp.display-item.citation.isi??? 60
social impact