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

Abstract

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

How to cite

top

Ausiello, 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.