# Comparing notions of approximation.

Mario Furnari; Antonio Massarotti

Stochastica (1988)

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

## Access Full Article

top## Abstract

top## How to cite

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

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