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.
@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/