Seminário de Otimização Combinatória


                 Algoritmo de Aproximação para o 
             Problema do Caixeiro Viajante Euclidiano


                       Fábio Pakk Selmi-Dei 

                      Sexta-feira, 28 de junho
                           sala: IC2-85    <----
                           horario: 18hs


Resumo:
=======

O problema do caixeiro viajante (TSP ou traveling salesman problem)
consiste em dado um grafo G=(V,E) e custos c em Q, para cada aresta e
em E, determinar um circuito hamiltoniano C que minimize o custo c(C).
O TSP Euclidiano é uma variação deste problema original, onde os
vértices de V correspondem a pontos no plano Euclidiano e o custo das
arestas c correspondem a distância euclidiana entre os pontos
correspondentes aos vértices no plano.  Graças a Arora (1996, 1997),
um esquema de aproximação em tempo polinomial (PTAS) foi concebido
para o TSP Euclidiano, capaz de encontrar um circuito hamiltoniano com
custo no máximo (1+\epsilon) em tempo polinomial.  A estratégia básica para
se obter a PTAS consiste em aplicar programação dinâmica. Ela também
funciona para diversos outros problemas, como o da árvore de Steiner
Euclidiana, casamento perfeito, k-MST e k-TSP.