Seminário de Teoria da Computação


     Esquema de Aproximação Polinomial para o Problema do
    Caixeiro Viajante Baseado na Subdivisão em Guilhotina
       

           Luis Augusto Angelotti Meira

         Sexta-feira, 27 de junho de 2003
           Auditório (IC1), 12:45hs

Sumário:

 Neste seminário vamos dissecar o artigo Guillotine Subdivisions
 Approximate Polygonal Subdivisions: A Simple Polynomial-Time
 Approximation Scheme for Geometric TSP, k-MST, and Related Problems
 de Joseph S. B. Mitchell. Trata-se de um trabalho sobre um PTAS
 (Polynomial Time Approximation Scheme) para o problema do Caixeiro
 Viajante TSP, conhecido problema NP-difícil. Foi provado que, para
 qualquer $\epsilon>0$ existe um algoritmo polinomial cuja solução se
 desvia, no máximo, $(1+\epsilon)$ do valor da solução ótima. A
 técnica utilizada foi divisão em guilhotina e pode ser extendida a
 outros problemas, como árvores de Steiner e $k$-MST