Título: O Problema do Corte Máximo.

Data: 27/11/2015 Horário: 10h Local: Sala de Seminários do Bloco 952 (Campus do Pici)

Resumo:

O foco dessa qualificação é o problema max-cut (corte máximo). Apresentamos diferentes formulações de programação matemática para o problema, encontradas na literatura, bem como mostramos relações entre elas. Algumas dessas formulações são quadráticas. Estendemos a técnica de t-linearização, desenvolvida originalmente para a maximização de funções quadráticas com coeficientes positivos, para funções quadráticas arbitrárias, de modo a aplicá-la a max-cut. Apresentamos condições necessárias ou suficientes para fixação de variáveis nas formulações, que podem traduzidas em desigualdades válidas. Propomos uma heurística gulosa que obtém um bom limite inferior, consumindo pouco tempo de computação. Realizamos experiências computacionais com a heurística e com três formulações, acrescidas ou não das desigualdades propostas, e comparamos os resultados com a literatura.

Banca:

• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC)
• Prof. Dr. Carlos Diego Rodrigues (DEMA/UFC)