Algoritmos de aproximación

Los algoritmos de aproximación resuelven problemas de optimización NP-hard en tiempo polinómico, garantizando una solución que se encuentra dentro de un factor fijo del óptimo, lo que establece compensaciones rigurosas entre la calidad de la solución y la tratabilidad.

Definition

Un algoritmo de aproximación para un problema de optimización es un algoritmo de tiempo polinómico que devuelve una solución factible cuyo valor objetivo está garantizado dentro de un factor multiplicativo probado —la razón de aproximación— del valor óptimo.

Scope

Este tema abarca los algoritmos de tiempo polinómico que devuelven soluciones casi óptimas a problemas de optimización difíciles, la razón de aproximación que mide su calidad y las principales técnicas de diseño: heurísticas voraces y de búsqueda local con límites demostrables, relajación y redondeo de programación lineal, y el método primal-dual. También cubre los esquemas de aproximación (PTAS y FPTAS) y la existencia de resultados de inaproximabilidad que limitan la calidad con la que se pueden aproximar algunos problemas.

Core questions

• ¿Cómo se mide la calidad de una solución aproximada mediante una razón de aproximación?
• ¿Cómo la relajación y el redondeo de la programación lineal transforman un óptimo fraccionario en una solución entera acotada?
• ¿Cómo los métodos voraces y de búsqueda local producen garantías de aproximación demostrables?
• ¿Qué son los esquemas de aproximación de tiempo polinómico y qué problemas los admiten?
• ¿Por qué algunos problemas pueden aproximarse arbitrariamente bien mientras que otros no pueden aproximarse en absoluto?

Key concepts

• razón de aproximación
• optimización NP-hard
• aproximación voraz
• búsqueda local
• relajación y redondeo de LP
• método primal-dual
• PTAS y FPTAS
• inaproximabilidad

Key theories

Razón de aproximación

La razón de aproximación limita cuán lejos puede estar la solución de un algoritmo del óptimo en el peor de los casos; una c-aproximación garantiza una solución dentro de un factor c del óptimo, proporcionando un certificado de calidad riguroso para un algoritmo eficiente.

Relajación y redondeo de LP

Muchos algoritmos de aproximación relajan un programa entero a un programa lineal, lo resuelven eficientemente y redondean la solución fraccionaria a una entera, acotando la pérdida, lo que produce razones demostrables a través de los marcos primal-dual o de redondeo.

Clinical relevance

Los algoritmos de aproximación hacen que la optimización intratable sea utilizable en la práctica: los métodos de razón acotada para la cobertura de conjuntos, la cobertura de vértices, la localización de instalaciones, la programación y el problema del viajante guían los sistemas reales en logística, diseño de redes e investigación de operaciones, proporcionando soluciones con garantías de calidad en lugar de heurísticas no verificadas.

History

El campo comenzó en la década de 1970, con el análisis de Johnson de las razones de aproximación para problemas como la cobertura de conjuntos y el empaquetamiento de contenedores, y el algoritmo de Christofides de 1976 para el problema del viajante métrico. Las técnicas de programación lineal y primal-dual maduraron en las décadas de 1980 y 1990, y las pruebas verificables probabilísticamente establecieron posteriormente fuertes resultados de inaproximabilidad, todo ello consolidado en los libros de texto de Vazirani y de Williamson y Shmoys.

Key figures

• Vijay Vazirani
• David Williamson
• David Shmoys
• David Johnson
• László Lovász

Seminal works

• vazirani2001
• williamson2011
• cormen2009

Frequently asked questions

¿Qué garantiza un algoritmo de 2-aproximación?

Para un problema de minimización, una 2-aproximación siempre devuelve una solución cuyo costo es como máximo el doble del costo óptimo (y al menos óptimo para un problema de maximización, dentro de un factor de la mitad). La garantía se mantiene para cada entrada, sin importar cuán adversa sea.

¿Se puede aproximar bien todo problema NP-hard?

No. Algunos problemas admiten esquemas de aproximación que se acercan arbitrariamente al óptimo, otros tienen una razón constante óptima posible, y algunos no pueden aproximarse dentro de ningún factor razonable a menos que P sea igual a NP. Los resultados de inaproximabilidad establecen formalmente estos límites.