Programa del Curso

Una gran parte de los problemas de optimización del mundo real pertenecen a la clase NP-difícil, en su mayoría problemas cuya versión de decisión pertenecen a la clase NP y por ende a la NP completa. Desde el punto de vista de soluciones exactas todos los problemas de decisión de la clase NP completa son igual de difíciles. Sin embargo, cuando estudiamos la eficiencia de los algoritmos para encontrar soluciones aproximadas vemos que la dificultad cambia radicalmente de un problema a otro: desde problemas que pueden ser eficientemente aproximados tanto como queramos hasta problemas que no admiten un factor constante de aproximación.

El concepto de aproximación al que nos referimos no tiene que ver con el concepto de aproximación usado en forma regular en las heurísticas o meta-heurísticas. Este concepto de aproximación exige que garanticemos matemáticamente que, en el peor caso, nuestro algoritmo generará soluciones por debajo de un cierto factor constante (mayor que uno) veces el óptimo del problema (en el caso de problemas de minimización).

Existen un gran número de técnicas de diseño de algoritmos de aproximación así como metodologías para determinar la cota de aproximación de los mismos. En este curso revisaremos los principios básicos de esta nueva y fascinante línea de investigación dentro de las ciencias de la computación. Este tema resulta normalmente interesante para estudiantes con un interés marcado en los algoritmos y las matemáticas.

OBJETIVO

Familiarizar al alumno con distintos métodos para la obtención de cotas de aproximación de algoritmos cuando estos son aplicados a problemas de la clase NP- difícil. Familiarizarlo también con algunas técnicas para transformaciones que preservan la cota de aproximación.

PREREQUISITOS

Conocimientos básicos de análisis de algoritmos.

DURACIÓN

15 horas

PROFESOR

Dr. Carlos A. Brizuela

CONTENIDO

  1. Fundamentos. (3 hrs.)
    • Revisión de complejidad computacional
    • Definición de algoritmo de aproximación
    • Obtención de cotas inferiores mediante ejemplos ilustrativos
  2. Algoritmos combinatorios. (5 hrs.)
    • Cubrimiento de conjuntos
    • Árbol de Steiner y el problema del viajante
    • La supercadena común más corta (SCS)
    • Esquema de aproximación para la mochila
    • Problemas de empaquetamiento
  3. Algoritmos basados en Programación Lineal (4 hrs.)
    • Redondeo aplicado al cubrimiento de vértices
    • Ejemplos en calendarización
    • Localización de plantas (Facility Location)
    • Bosque y red de Steiner
  4. Extensiones. (3 hrs.)
    • Algoritmos aleatorios
    • Dificultad de aproximación
    • Aproximación en problemas multi-objetivo

BIBLIOGRAFÍA

Cada tópico del contenido está incluido en el siguiente texto:

  1. Vijay V. Vazirani. Approximation Algorithms, Springer, 2003.

Material de apoyo:

  1. Dorit S. Hochbaum, editor. Approximation algorithms for NP-hard Problems. PWS Publishing, 1997.
  2. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999.
  3. Juraj Hromkovic . Algorithmics for Hard Problems: Introduction to Combinatorial Optimization Randomization, Approximation, and Heuristics. Springer, 2002.