Comparing notions of approximation.

Mario Furnari; Antonio Massarotti

Stochastica (1988)

  • Volume: 12, Issue: 1, page 19-31
  • ISSN: 0210-7821

Abstract

top
In this note we discuss some drawbacks of some approaches to the classification of NP-complete optimization problems. Then we analyze the Theory of Analytical Computational Complexity to gain some insight about the notions of approximation and approximate algorithms. We stress the different roles played by these notions within the theories of Analytical and Algebraic Complexity. We finally outline a possible strategy to capture a more useful notion of approximation which is inspired by some results on Linear Programming problems.

How to cite

top

Furnari, Mario, and Massarotti, Antonio. "Comparing notions of approximation.." Stochastica 12.1 (1988): 19-31. <http://eudml.org/doc/39009>.

@article{Furnari1988,
abstract = {In this note we discuss some drawbacks of some approaches to the classification of NP-complete optimization problems. Then we analyze the Theory of Analytical Computational Complexity to gain some insight about the notions of approximation and approximate algorithms. We stress the different roles played by these notions within the theories of Analytical and Algebraic Complexity. We finally outline a possible strategy to capture a more useful notion of approximation which is inspired by some results on Linear Programming problems.},
author = {Furnari, Mario, Massarotti, Antonio},
journal = {Stochastica},
keywords = {Optimización; Algoritmos; Aproximación; NP-complete optimization problems; Analytical Computational Complexity; approximate algorithms; Linear Programming problems},
language = {eng},
number = {1},
pages = {19-31},
title = {Comparing notions of approximation.},
url = {http://eudml.org/doc/39009},
volume = {12},
year = {1988},
}

TY - JOUR
AU - Furnari, Mario
AU - Massarotti, Antonio
TI - Comparing notions of approximation.
JO - Stochastica
PY - 1988
VL - 12
IS - 1
SP - 19
EP - 31
AB - In this note we discuss some drawbacks of some approaches to the classification of NP-complete optimization problems. Then we analyze the Theory of Analytical Computational Complexity to gain some insight about the notions of approximation and approximate algorithms. We stress the different roles played by these notions within the theories of Analytical and Algebraic Complexity. We finally outline a possible strategy to capture a more useful notion of approximation which is inspired by some results on Linear Programming problems.
LA - eng
KW - Optimización; Algoritmos; Aproximación; NP-complete optimization problems; Analytical Computational Complexity; approximate algorithms; Linear Programming problems
UR - http://eudml.org/doc/39009
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.