Buenas Estudiantes,
Hoy vimos un algoritmo de factor 2 para el cubrimiento de vértices de mínimo cardinsl.
El algoritmo es muy sencillo, y consiste en retornar los vértices que son extremo de un emparejamiento maximal.
Vimos luego que el factor 2 de tal algoritmo no se puede mejorar tomando distintos emparejamientos, tras analizar su rendimiento para grafos bipartitos completos. La mejora del factor 2 para el cubrimiento de vértices de mínimo cardinal es un famoso problema abierto del área de Algoritmos de Aproximación.
Luego estudiamos el problema de cubrimiento de conjuntos, que es una generalización. Probamos que el algoritmo goloso asegura un factor armónico para tal problema, y hemos construido instancias de "peor caso", donde se burla al algoritmo goloso.
Más adelante veremos generalizaciones utilizando la teoría de programación lineal.
En la clase que viene vamos a construir algoritmos de aproximación para el TSP y para el problema de Steiner.
También veremos sugerencias para abordar los ejercicios 3 y 4 de la lista de 10 ejercicios.
Nos vemos el lunes que viene a las 18:00 en el Salón 725.
Cordiales saludos,
Pablo.