This HTML5 document contains 24 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Subject Item

dbpedia-es:Algoritmo_aproximado

dbo:wikiPageRedirects

dbpedia-es:Algoritmo_de_aproximación

Subject Item

dbpedia-es:Algoritmo_de_aproximacion

dbo:wikiPageRedirects

dbpedia-es:Algoritmo_de_aproximación

Subject Item

dbr:Approximation_algorithm

owl:sameAs

dbpedia-es:Algoritmo_de_aproximación

Subject Item

wikipedia-es:Algoritmo_de_aproximación

foaf:primaryTopic

dbpedia-es:Algoritmo_de_aproximación

Subject Item

dbpedia-es:Algoritmo_de_aproximación

rdfs:label

Algoritmo de aproximación

rdfs:comment

En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización. Están a menudo asociados con problemas NP-hard; como es poco probable que alguna vez se descubran algoritmos eficientes de tiempo polinómico que resuelvan exactamente problemas NP-hard, se opta por encontrar soluciones no-óptimas en tiempo polinomial. A diferencia de las , que usualmente solo encuentran soluciones razonablemente buenas en tiempos razonablemente rápidos, lo que se busca aquí es encontrar soluciones que está demostrado son de calidad y cuyos tiempos de ejecución están acotadas por cotas conocidas. Idealmente, la aproximación mejora su calidad para factores constantes pequeños (por ejemplo, dentro d

owl:sameAs

n12:02qc78

dct:subject

category-es:Algoritmos category-es:Complejidad_computacional

foaf:isPrimaryTopicOf

wikipedia-es:Algoritmo_de_aproximación

prop-es:apellidos

Vazirani

prop-es:editorial

Springer

prop-es:enlaceautor

Vijay Vazirani

prop-es:fecha

2003

prop-es:isbn

3540653678

prop-es:nombre

Vijay V.

prop-es:título

Approximation Algorithms

prop-es:ubicación

Berlin

dbo:wikiPageID

1751610

dbo:wikiPageRevisionID

127973086

dbo:wikiPageExternalLink

n15:

dbo:wikiPageLength

6797

prov:wasDerivedFrom

n14:0

dbo:abstract

En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización. Están a menudo asociados con problemas NP-hard; como es poco probable que alguna vez se descubran algoritmos eficientes de tiempo polinómico que resuelvan exactamente problemas NP-hard, se opta por encontrar soluciones no-óptimas en tiempo polinomial. A diferencia de las , que usualmente solo encuentran soluciones razonablemente buenas en tiempos razonablemente rápidos, lo que se busca aquí es encontrar soluciones que está demostrado son de calidad y cuyos tiempos de ejecución están acotadas por cotas conocidas. Idealmente, la aproximación mejora su calidad para factores constantes pequeños (por ejemplo, dentro del 5% de la solución óptima). Los algoritmos de aproximación están siendo cada vez más utilizados para resolver problemas donde los algoritmos exactos de tiempo polinomial son conocidos pero demasiado costosos debido al tamaño de la entrada. Un ejemplo típico para un algoritmo de aproximación es uno para resolver el problema de la cobertura de vértices de la teoría de grafos: encontrar una arista no cubierta y añadir sus dos puntos finales a la cobertura de vértice, y repetir hasta que ya no queden aristas. Es claro que la cobertura resultante será a lo más dos veces del largo de la solución óptima. Este es un con un factor de 2. Los problemas NP-hard varían mucho en su aproximación; algunos, tales como el problema de la mochila, pueden ser aproximados mediante cualquier factor superior a 1 (tal familia de algoritmos de aproximación se conoce como o PTAS). Otros, como el problema de la clique, son imposibles de aproximar dentro de cualquier constante, o incluso factor polinomiales, a menos que P = NP. Los problemas NP-hard frecuentemente pueden expresarse como programación entera (PE) y ser resueltos exactamente en tiempo exponencial. Muchos algoritmos de aproximación surgen de la relajación de la programación lineal (PL), propia de la programación entera. No todos los algoritmos de aproximación son adecuados para todas las aplicaciones prácticas. A menudo utilizan resolvedores (solvers) de IP, LP y programación semidefinida, estructuras de datos complejas o técnicas de algoritmos sofisticadas que tienden a dificultar los problemas de implementación. Además, algunos algoritmos de aproximación poseen tiempos de ejecución poco prácticos, incluso a pesar de ser polinómicos, como por ejemplo, del orden de O(n2000). Sin embargo, a pesar de esto último, existen problemas donde los altos tiempos de ejecución y costos de memoria pueden justificarse, tales como los relacionados con la biología computacional, ingeniería financiera, la planificación del transporte, y la gestión de inventario. En estos escenarios, se debe competir contra las correspondientes formulaciones de programación entera directa. Otra limitación de la aproximación es que esta solo es aplicable a los problemas de optimización, y no a los problemas de decisión en estado "puro", tales como SAT (a pesar de que es posible representar versiones de optimización para tales problemas, como el respectivo ).