Novedades

Buenas Estudiantes,

A continuación van algunas sugerencias para abordar los 13 ejercicios de la lista.

Ejercicio 1) Este es un resultado clásico sobre matrices totalmente unimodulares. Se puede demostrar empleando el principio de inducción completa sobre el tamaño de la submatriz cuadrada.

Ejercicio 2) Aplicar el algoritmo sugerido en la última diapositiva de la clase 3 a una instancia cualquiera $I_2$ del problema $\Pi_2$ y utilizar las hipótesis.

Ejercicios 3 y 4) Seguir las sugerencias indicadas en la clase 5.

Ejercicio 5) Traducir los problemas descriptos al MST cuando $S\cup R=V$, o al problema de Steiner cuando $S\cup R\neq V$. 

Ejercicio 6) Leer el artículo sobre la Historia del Problema de Steiner Euclídeo disponible aquí.

Ejercicio 7) Dado un grafo $G=(V,E)$, el MAX-$k$-CUT consiste en encontrar la partición de vértices $V=\cup_{i=1}^{k}A_i$ que tiene la máxima cantidad de aristas en $E$ con un extremo en algún $A_i$ y un extremo en algún $A_j$ tal que $i\neq j$. Se recomienda seleccionar inicialmente $k$ vértices cualesquiera $v_1,v_2,\ldots,v_k$ de $V$, definir inicialmente  $A_i=\{v_i\}$ para cada $i\in \{1,2,\ldots,k\}$ y luego agregar de manera golosa a todos los restantes vértices de $V$.

Ejercicio 8) Formular el problema primal siguiendo el Ejercicio 12.10 del libro de Vazirani. Sea  $e_1,e_2,\ldots,e_m$ el conjunto de aristas que elige Kruskal con costos $c(e_1),c(e_2),\ldots,c(e_n)$ y sea $A_i=\{e_1,\ldots,e_i\}$. Notar que $A_m=E$. 

Mostrar que la tupla $y$ dada por $y_{A_i}=c(e_{i+1})-c(e_i)$ para cada $i\in \{1,2,\ldots,m-1\}$, mientras que $y_{A_m}=y_{E}=-c(e_m)$ o $y_{X}=0$ para cualquier otro subconjunto $X$ de $E$ es solución factible dual. Utilizar esta solución para resolver el ejercicio empleando resultados de dualidad.  

Ejercicio 9) Seguir las sugerencias del Ejercicio 12.11 del libro de Vazirani.

Ejercicio 10) Recordar la existencia de algoritmos de aproximación para el problema de Redes de Steiner.

Ejercicio 11: En el libro de Vazirani se detalla una formulación del problema de cubrimiento de vértices de mínimo peso como problema de programación lineal entera. Duplicar la solución óptima del problema relajado.

Ejercicio 12: Probar primero existencia de alguna solución. Luego, mostrar que si dos coordenadas de 

$p=(p_1,p_2,\ldots,p_n)$ no son idénticas entonces $p$ no alcanza el máximo.

Ejercicio 13: Aplicar directamente la definición de supermodularidad débil. 

Cordiales saludos,

Pablo.