Buenas noches estudiantes,
¡Fue muy gratificante para mí tener el primer encuentro del curso Algoritmos de Aproximación!
Nos conocimos con Franco y con Federico; con Mauro ya nos conocíamos, quien también asistió a la clase de hoy.
A quienes no vinieron les pido por favor que me digan si les es viable cambiar los encuentros de los jueves para los miércoles a la misma hora, es decir, miércoles de 18:00 a 19:30 (con una hora adicional libre para consultas). Esto es justamente porque Mauro tiene otro curso que solapa el horario los jueves. Dado que somos pocos, me gustaría que busquemos un horario que nos sea posible para todas/os.
Aprovecho para recordar que la asistencia a este curso es importante (tener al menos un 80% de asistencia a las clases es requisito para aprobar). Por otra parte, también comenté que dando un seguimiento del curso es bien llevadera la aprobación. Voy a dar piques para resolver ejercicios a entregar, y varios temas de libre elección para que puedan exponer al final del curso.
En la clase de hoy vimos el génesis y la motivación del curso. Mencionamos problemas célebres históricos en la clase 
como el problema de maximizar flujos en redes, camino mínimo entre dos vértices de un grafo, algoritmo de reconocimiento de un grafo bipartito (DFS), construcción de circuitos eulerianos y determinación de emparejamientos de máximo (o mínimo) peso en un grafo.
Vimos, por ahora de modo informal, el concepto de problema de optimización combinatoria. Enunciamos el problema del Mochilero o el "Knapsack Problem" mediante programación lineal entera. También mostramos un ejemplo en tamaño miniatura de TSP (Problema de Vendedor ambulante) y su importancia práctica. Vimos que el algoritmo goloso para el TSP no es óptimo a partir de un ejemplo de grafos simple pesado con 4 vértices. Formulamos un problema de asignación de viviendas para núcleos familiares en cooperativas de viviendas mediante un problema de programación lineal entera. Mencionamos que el método húngaro de Kuhn permite encontrar un emparejamiento de máximo peso en un grafo bipartito, mientras que el algoritmo de Edmonds también permite encontrar un emparejamiento de máximo o mínimo peso en cualquier grafo simple, en tiempo polinomial.
En esta clase no hubo ejercicios, aunque les comenté que la técnica de "duplicación" de aristas en cualquier grafo simple determina un multigrafo que siempre admite un circuito euleriano, y que es un elemento a tener en consideración para resolver algún ejercicio de los que veremos más adelante.
Mencionamos 5 problemas de optimización combinatoria de clase 
-difícil que trataremos durante el curso y de los cuales estudiaremos su aproximabilidad, a saber, el TSP o vendedor ambulante, el cubrimiento de vértices de mínimo cardinal, el problema de cubrimiento de conjuntos, el problema de Steiner y el problema de diseño de subredes recubridoras 2-conexas de costo mínimo.
Comentamos la importancia del teorema fuerte de dualidad en programación lineal y la teoría de emparejamientos como fuentes de inspiración para construir algoritmos de aproximación. Por otro lado, hemos comentado la importancia de los problemas minimax y sus equivalencias, que componen lo que se llama el teorema fundamental de la combinatoria. La clase que viene vamos a probar un importante teorema minimax, que es el Teorema de Konig, utilizando dualidad fuerte y la noción de integralidad de un problema de programación lineal entera.
Aguardo para saber si les es viable el cambio de los jueves a las 6pm para los miércoles a las 6pm.
¡Que tengan una muy buena semana, y que disfruten mucho del curso!
Cordiales saludos,
Pablo.