Full approximability of a class of problems over power sets.

Título inglés	Full approximability of a class of problems over power sets.
Título español	Aproximabilidad completa de una clase de problemas sobre conjuntos potencias.
Autor/es	Ausiello, Giorgio ; Marchetti-Spaccamela, Alberto ; Protasi, Marco
Organización	Ist. Autom. Univ. Roma, Roma, Italia;Cent. Stud. Sist. Contr. Calc. Autom. [CNR], Roma, Italia;Ist. Mat. Univ. dell'Aquila, L'Aquila, Italia
Revista	0210-8054
Publicación	1981, 5 (1): 5-11, 8 Ref.
Tipo de documento	articulo
Idioma	Inglés
Resumen inglés	In this paper results concerning structural and approximability properties of the subclass of NP-Complete Optimization Problems, defined over a lattice are considered. First, various approaches to the concept of Fully Polynomial Approximation Scheme are presented with application to several known problems in the class of NP-Complete Optimization Problems. Secondly, a characterization of full Approximability for the class of Max Subset Problems is introduced.
Clasificación UNESCO	120601
Palabras clave español	Optimización ; Problemas combinatorios ; Aproximabilidad ; Retículo
Acceso al artículo completo