Resolver tres de los siguientes cinco problemas. Entregar en clase el 9 de julio.

1. Subgráfica acíclica: Dada una gráfica dirigida D = (V, A), seleccionar un subconjunto de arcos de cardinalidad máxima de modo que la subgráfica resultante sea acíclica. Objetivo: Proponer un algoritmo de aproximación con garantía 1/2. Pista: Ordene los vértices de forma arbitraria y considere dos subconjuntos de los arcos según para dónde apunten.
2. Acoplamiento maximal mínimo: Dada una gráfica no dirigida G = (V, E), un acoplamiento M es maximal si no se le pueden agregar aristas de modo que siga siendo acoplamiento. Se desea encontrar un acoplamiento maximal M con el mínimo número de aristas. Objetivo: Proponer un algoritmo de aproximación con garantía 2. Pista: ¿Cómo se compara el tamaño de un acoplamiento maximal con el tamaño de un acoplamiento máximo?
   
3. Coloración de gráficas tricromáticas: Dada una gráfica no dirigida G = (V, E) tal que es 3-coloreable por vértices. Objetivo: Dar una coloración de los vértices de G con O(n^1/2) colores. Pista: Si G es 3-colorable entonces los vecinos N(v) de cualquier vértice v forman una gráfica bipartita. Si v tiene grado mayor a n^1/2, entonces colorear óptimamente v y N(v) y borrar esto de G. Continuar hasta que todos los vértices tengan grado a lo mucho n^1/2. ¿Cómo colorear lo que queda con O(n^1/2) colores?
4. Mochila glotona 1: Suponga que los objetos están ordenados de forma decreciente de acuerdo a la división p_i/s_i. Ahora escoja los objetos en este orden de forma glotona. Demuestre que este algoritmo no tiene garantía de aproximación. Pista: Debe dar una familia infinita de ejemplos para los cuales siempre haya alguno tan malo como uno quiera.
5. Mochila glotona 2: Suponga que los objetos están ordenados de forma decreciente de acuerdo a la división p_i/s_i. Suponga que los objetos a₁, ..., a_k-1 caben en la mochila pero a₁, ..., a_k no caben. Emita como salida al mejor de {a₁, ..., a_k-1} y {a_k}. Demuestre que este algoritmo tiene garantía de aproximación 2.