1. No category

Cubrimiento de Vértices
Steiner y MST
Algoritmos de Aproximación
Clase 3
Problema de Steiner y TSP
Pablo Romero
Lunes 8 de agosto de 2016, Montevideo, Uruguay.
Cubrimiento de Vértices
Contenidos
1
Cubrimiento de Vértices
2
Steiner y MST
Steiner y MST
Cubrimiento de Vértices
Agenda
1
Cubrimiento de Vértices
2
Steiner y MST
Steiner y MST
Cubrimiento de Vértices
Steiner y MST
Definición
Definición
Emparejamientos y Cubrimientos
Sea G = (V , E ) un grafo simple.
Un emparejamiento es un subconjunto de aristas M ⊆ E que
no tiene nodos comunes.
Un emparejamiento perfecto es un emparejamiento M que
visita a todos los nodos de V .
Un cubrimiento de vértices es un conjunto V 0 ⊆ V que visita
todas las aristas E .
Observación:
Un emparejamiento M tiene menos aristas que el perfecto:
|M| ≤ |V |/2.
Cubrimiento de Vértices
Steiner y MST
Definición
Problema
Cubrimiento de vértices
Sea G = (V , E ) un grafo simple. Hallar el cubrimiento de vértices
V 0 ⊆ V con mínimo cardinal.
Pregunta
Existe un vínculo entre emparejamientos y cubrimientos?
Cubrimiento de Vértices
Steiner y MST
Algoritmo de Factor 2
Algoritmo de Factor 2
Teorema
Sea VM los nodos visitados por un emparejamiento maximal M.
Luego |VM | ≤ vmin /2.
Prueba. Sea V 0 un cubrimiento con |V 0 | = vmin . Para cubrir la
arista (x , y ) ∈ M, el conjunto V 0 debe contener al menos x o y .
Luego |V 0 | ≥ |M|. Por definición |VM | = 2|M| ≤ 2vmin . La
maximalidad de M asegura que |VM | visita a todas las aristas, y es
por tanto un cubrimiento.
Q.E.D.
Cubrimiento de Vértices
Algoritmo de Factor 2
Preguntas
Preguntas
Es posible mejorar el factor con otro análisis?
Es posible tomar mejores emparejamientos?
Es posible construir otro algoritmo con mejor factor?
Steiner y MST
Cubrimiento de Vértices
Agenda
1
Cubrimiento de Vértices
2
Steiner y MST
Steiner y MST
Cubrimiento de Vértices
Steiner y MST
Definición de Problemas
Definición de Problemas
Definición de Problemas
Sea G = (V , E ) un grafo simple con costos no negativos en sus
aristas.
TSP: hallar el ciclo Hamiltoniano de menor costo.
MST: hallar el árbol recubridor de menor costo.
Steiner: si V = S ∪ T , hallar un subgrafo recubridor de T de
menor costo.
Cubrimiento de Vértices
Steiner y MST
Definición de Problemas
Algoritmo Goloso
Toma iterativamente aristas de menor costo, hasta construir la
solución. Asumiendo que el grafo de entrada es métrico, tenemos
el siguiente rendimiento:
Algoritmo Goloso
Es óptimo en el MST (Kruskal).
Es subóptimo en el TSP (ej. un rombo).
Consigue factor 2 en el Problema de Steiner.
Cubrimiento de Vértices
Steiner y MST
Factor 2 en Steiner
Problema de Steiner: Factor 2
Teorema
El algoritmo goloso entrega el MST de la clausura, y consigue un
factor 2.
Prueba. Sea T un árbol con costo OPT . Al duplicar sus aristas,
podemos encontrar un circuito de Euler con costo 2OPT .
Armemos un ciclo de Hamilton de R tomando atajos. Su costo es
inferior a 2OPT . Al eliminarle una arista tenemos un camino en R,
cuyo costo no es menor que el MST de la clausura.
Q.E.D.
Cubrimiento de Vértices
Steiner y MST
Factor 2 en TSP Métrico
TSP Métrico: Factor 2
La construcción anterior sugiere un algoritmo de factor 2:
TSP Métrico - Factor 2
Hallar un MST
Duplicar Aristas
Hallar un circuito de Euler E.
Entregar el ciclo C según aparición en E.
La demostración del factor 2 es similar a la anterior. La clave es
notar que el costo del MST no supera OPT .
Pista
Hay una manera más económica de construir el circuito de Euler,
usando el MST?
Cubrimiento de Vértices
Steiner y MST
Factor 3/2 en TSP Métrico
Algoritmo de Christofides
TSP Métrico - Factor 3/2
Hallar un MST, T . Sea
V 0 = {v ∈ T : deg(v ) = 2k + 1, k ∈ Z}.
Hallar un matching de mínimo costo Mopt para V 0 .
Hallar un circuito de Euler E en T ∪ M.
Entregar el ciclo C según aparición en E.
Teorema
c(Mopt ) ≤ c(Copt )/2
Prueba. Tomando atajos en Copt tenemos dos matchings para V 0 .
Q.E.D.
Cubrimiento de Vértices
Problemas Abiertos
Preguntas
Preguntas
Se puede mejorar el factor 2 en emparejamientos?
El problema de Steiner admite un mejor factor?
Se puede mejorar el algoritmo de Christofides?
El TSP métrico admite un PTAS?
Qué ocurre en casos no métricos?
Steiner y MST