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