Fernando Mário de Oliveira Filho
CWI (Amsterdam)
Sexta-feira, 15 de junho de 2007, 14:00
Anfiteatro do NUMEC-USP
Resumo:
Programação semidefinida é uma generalização de programação linear que tem-se tornado popular no tratamento de diversos problemas combinatórios, como por exemplo na obtenção de limitantes inferiores para o número cromático de grafos.
Do ponto de vista prático, mesmo problemas de programação semidefinida de tamanho moderado são difíceis de resolver. Entretanto, em muitas aplicações, os problemas apresentam grande simetria, que pode ser explorada para diminuir o número de variáveis consideravelmente. Neste seminário vamos apresentar idéias propostas por Schrijver, baseadas também em idéias de outros autores, que podem ser usadas para explorar a simetria de problemas de programação semidefinida. Tais idéias fazem uso de ferramentas algébricas, como teoria de representação de grupos.
Se houver tempo, mostraremos uma aplicação das idéias expostas ao problema de encontrar-se cotas superiores para o tamanho de códigos binários corretores de erros.