Dureza de aproximación - Hardness of approximation
En informática , la dureza de la aproximación es un campo que estudia la complejidad algorítmica de encontrar soluciones casi óptimas a los problemas de optimización .
Alcance
La dureza de la aproximación complementa el estudio de los algoritmos de aproximación al demostrar, para ciertos problemas, un límite en los factores con los que su solución puede aproximarse de manera eficiente. Típicamente, dichos límites muestran un factor de aproximación a partir del cual se convierte en un problema NP-duro , lo que implica que la búsqueda de un tiempo polinómico aproximación para el problema es imposible a menos que NP = P . Sin embargo, cierta dureza de los resultados de aproximación se basan en otras hipótesis, entre las cuales destaca la conjetura de juegos únicos .
Historia
Desde principios de la década de 1970 se sabía que muchos problemas de optimización no podían resolverse en tiempo polinomial a menos que P = NP , pero en muchos de estos problemas la solución óptima podía aproximarse eficientemente hasta cierto punto. En la década de 1970, Teófilo F. González y Sartaj Sahni comenzaron el estudio de la dureza de aproximación, mostrando que ciertos problemas de optimización eran NP-difíciles incluso para aproximarse dentro de una relación de aproximación dada . Es decir, para estos problemas, existe un umbral tal que cualquier aproximación polinomial-temporal con una relación de aproximación más allá de este umbral podría usarse para resolver problemas NP-completos en tiempo polinomial. A principios de la década de 1990, con el desarrollo de la teoría de la PCP , quedó claro que muchos más problemas de aproximación eran difíciles de aproximar y que (a menos que P = NP) muchos algoritmos de aproximación conocidos lograban la mejor relación de aproximación posible.
La teoría de la dureza de la aproximación se ocupa del estudio del umbral de aproximación de tales problemas.
Ejemplos
Para ver un ejemplo de un problema de optimización NP-hard que es difícil de aproximar, consulte la portada del conjunto .
Ver también
Referencias
Otras lecturas
- Trevisan, Luca (27 de julio de 2004), Inaproximabilidad de problemas de optimización combinatoria (PDF)
enlaces externos
- CSE 533: The PCP Theorem and Hardness of Approximation, otoño de 2005 , programa de estudios de la Universidad de Washington , Venkatesan Guruswami y Ryan O'Donnell