Full approximability of a class of problems over power sets.
Ausiello, Giorgio ; Marchetti-Spaccamela, Alberto ; Protasi, Marco
Qüestiió, Tome 5 (1981), p. 5-11 / Harvested from Biblioteca Digital de Matemáticas

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.

Publié le : 1981-01-01
DMLE-ID : 2639
@article{urn:eudml:doc:39972,
     title = {Full approximability of a class of problems over power sets.},
     journal = {Q\"uestii\'o},
     volume = {5},
     year = {1981},
     pages = {5-11},
     zbl = {0469.68055},
     language = {en},
     url = {http://dml.mathdoc.fr/item/urn:eudml:doc:39972}
}
Ausiello, Giorgio; Marchetti-Spaccamela, Alberto; Protasi, Marco. Full approximability of a class of problems over power sets.. Qüestiió, Tome 5 (1981) pp. 5-11. http://gdmltest.u-ga.fr/item/urn:eudml:doc:39972/