Seminário de Otimização Combinatória Flavio Keidi Miyazawa Sexta-feira, 24 de maio sala: IC2-96 horario: 18hs Um algoritmo 0,878-aproximado para o problema do corte maximo. Neste seminario apresentaremos um algoritmo desenvolvido por Goemans e Williamson'94 usando programacao semidefinida para o problema do corte maximo. Dado um grafo com pesos nas arestas, particionar o conjunto de seus vertices em duas partes, de maneira a maximizar o peso das arestas que ligam vertices em partes distintas. O algoritmo apresenta um fator de aproximacao probabilistico de 0,878, que pode ser desaleatorizado.