Novedades

¡¡Les doy la bienvenida al curso de Algoritmos de Aproximación en su edición de 2023!!

Este curso es una invitación a explorar el mundo de la optimización, clasificando problemas según si admiten una solución exacta y eficiente, una noción de aproximabilidad, o ninguna de las anteriores.

Existe una mujer muy longeva y empoderada que se ha nutrido de conversaciones con Petersen, Konig, Kuhn y Edmonds, y nadie como ella es capaz de organizar el mundo de forma exacta y eficiente mediante asignaciones o correspondencias.
Ella se llama la Teoría de Emparejamientos.

Otra teoría muy potente se llama Programación Lineal, que ha mantenido conversaciones hace más de 90 años con Kantorovich y una intensa maduración entre 1946 y 1947 mediante intercambios con Dantzig. Esta teoría se enorgullece de ser una generalización del Algebra Lineal. 

Algunos problemas se resistieron a las técnicas desarrolladas por las poderosas Teorías anteriores. Turing, Cook y Karp han concebido una manera de clasificar esos intrincados problemas, dando nacimiento a inicios de la década del 70' a la Teoría de la Complejidad.

Los Algoritmos de aproximación son nietos de las tres teorías anteriores. Por un lado, la Teoría de Emparejamientos es su musa inspiradora. 
Konig, Dilworth, Fulkerson, Edmonds, Lovasz y luego otras personalidades, mediante diversas consultas realizadas a la teoría de la Programación Lineal, notaron que existe una suerte de "dualidad" entre emparejamientos y cubrimientos, describiendo esos objetos en términos de grafos. Sus avances por suerte quedaron registrados en Actas (Dilworth lo hizo en Annals of Mathematics) y en libros (Konig escribió el primer libro en la historia de la Teoría de Grafos y Lovasz rinde un homenaje a la Teoría de Emparejamientos junto con Plummer en un rico y profundo libro de referencia). Dichos algoritmos de aproximación permiten clasificar de modo más fino a aquellos problemas "difíciles", o "aparentemente intratables", de la Teoría de la Complejidad.

En este curso vamos a ver una introducción a los algoritmos de aproximación. La iniciativa de este curso nace a raíz de un bonito curso titulado "Approximation Algorithms" por un contribuyente en el área, el Profesor Maurice Queyranne. Ese curso fue ofrecido en nuestra Casa de Estudios, la Facultad de Ingeniería, por el año 2009.  Tal fue mi admiración por ese curso, que luego en 2016 se ha ofrecido este curso por quien escribe. Ahora en 2023, y nuevamente siendo principiante en el tema, me propongo ofrecer un espacio para comprender juntos algunos Algoritmos de Aproximación.

A modo de convite se acaban de subir unas diapositivas relativas a las primeras 4 clases. En la primera clase vamos a conocernos y a repasar la teoría de grafos, que es el lenguaje sobre el cual se describen diversos problemas de optimización combinatoria. En la segunda clase estudiaremos el Teorema de Konig y mencionaremos algunos teoremas minimax equivalentes. En el libro de Lovasz se expone una prueba basada en teoría de grafos; de hecho el mismo Konig ha escrito el primer libro en la historia de la teoría de grafos, y su teorema que versa  sobre emparejamientos y cubrimientos es una pieza más de dicha teoría. En el curso veremos una demostración del Teorema de Konig basada en la Teoría de Programación Lineal (concretamente, en el teorema fuerte de discrepancia 0 y las propiedades de matrices totalmente unimodulares, que eran ya conocidas por Poincaré).

En la tercera clase veremos el concepto de algoritmo de aproximación. Antes, veremos el significado de problema de optimización combinatoria y vamos a familiarizarnos con los 5 problemas que estudiaremos en el curso desde el punto de vista de estructuras combinatorias (luego volveremos a estudiar esos 5 problemas junto con otros mediante un esquema dual-primal que se deduce a partir de la programación lineal). También veremos nociones de complejidad computacional, la reducibilidad de Karp para probar que un problema de decisión es NP-difícil y el concepto de reducción que preserva el factor de aproximación (dos reducciones de naturaleza diferente, pero ambas permiten clasificar problemas). 

En la cuarta clase veremos los primeros algoritmos de aproximación del curso, aplicables al problema del cubrimiento de vértices de mínimo cardinal (el algoritmo que veremos se inspira fuertemente en el Teorema de Konig, que es un pilar de la teoría de emparejamientos para grafos bipartitos) y al problema de cubrimiento de conjuntos, que es una generalización del problema anterior. Vamos a construr un algoritmo de factor armónico para el cubrimiento de conjuntos.

En las semanas que siguen voy a ir subiendo nuevas diapositivas y lecturas complementarias. Próximamente voy a subir ejercicios para un mejor seguimiento de los contenidos del curso. Durante las clases se van a dar sugerencias para la resolución de dichos ejercicios.

¡¡Que disfruten mucho de este curso!!
Cordialmente,
Pablo.