Problema 1: resuelto en clase (es una invitación a repasar)
Problema 2: también fue resuelto en clase (probando que el cubrimiento de vértices es un caso especial de cubrimiento de conjuntos, y usando el factor armónico para el problema más general)
Problema 3: se toma correcto resolviendo el problema para cardinales.
a) Mostrar que todo óptimo local en MAX CUT logra factor 1/2 (la clave: contar grados internos y externos de cada nodo)
b) Generalizar, mostrando que todo óptimo local en MAX k CUT logra factor 1-1/k
(analizar grados internos y externos de un óptimo local)
Problema 4: el análisis es similar al algoritmo goloso para el cubrimiento de conjuntos.
Problema 5: está en la lista de problemas de Queyranne. Mi resolución está publicada (les invito a que piensen el problema y vean si lo resolvimos de la misma manera).
Problema 6: Si tienen un nodo de Steiner con segmentos salientes que forman un ángulo menor que 120 grados, pueden reemplazarlo por otro de 120 grados con menor longitud total. Luego se deben tener todos (tres) ángulos de 120 grados, y el nodo de Steiner debe tener grado 3. Completar el argumento geométrico calculando distancias.
Problema 7: Interpretar la formulación del MST como programa lineal del libro de Vazirani. Expresar el problema dual y las correspondientes relaciones de complementariedad. Interpretar en términos del algoritmo goloso. Comparar con los pasos de resolución sugeridos en el libro.
Problema 8: Leer cuidadosamente el último problema del Capítulo 12 del libro. Interpretar el problema de Teoría de Juegos como un problema de programación lineal. Tomar el dual, y usar el teorema de dualidad fuerte.
Problema 9: El algoritmo de Goemans-Williamson será presentado al final del curso. Se sugiere atender la presentación para demostrar el factor 2 aquí pedido.
Problema 10: Seguir atentamente los pasos del problema 23.25 del libro.