# Full approximability of a class of problems over power sets.

Giorgio Ausiello; Alberto Marchetti-Spaccamela; Marco Protasi

Qüestiió (1981)

- Volume: 5, Issue: 1, page 5-11
- ISSN: 0210-8054

## Access Full Article

top## Abstract

top## How to cite

topAusiello, Giorgio, Marchetti-Spaccamela, Alberto, and Protasi, Marco. "Full approximability of a class of problems over power sets.." Qüestiió 5.1 (1981): 5-11. <http://eudml.org/doc/39972>.

@article{Ausiello1981,

abstract = {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.},

author = {Ausiello, Giorgio, Marchetti-Spaccamela, Alberto, Protasi, Marco},

journal = {Qüestiió},

keywords = {Optimización; Problemas combinatorios; Aproximabilidad; Retículo; approximate algorithms for NP-complete optimization problems; max-subset problems; full approximability},

language = {eng},

number = {1},

pages = {5-11},

title = {Full approximability of a class of problems over power sets.},

url = {http://eudml.org/doc/39972},

volume = {5},

year = {1981},

}

TY - JOUR

AU - Ausiello, Giorgio

AU - Marchetti-Spaccamela, Alberto

AU - Protasi, Marco

TI - Full approximability of a class of problems over power sets.

JO - Qüestiió

PY - 1981

VL - 5

IS - 1

SP - 5

EP - 11

AB - 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.

LA - eng

KW - Optimización; Problemas combinatorios; Aproximabilidad; Retículo; approximate algorithms for NP-complete optimization problems; max-subset problems; full approximability

UR - http://eudml.org/doc/39972

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.