Banca de DEFESA: TEOBALDO LEITE BULHOES JUNIOR

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: TEOBALDO LEITE BULHOES JUNIOR
DATA: 21/07/2015
HORA: 16:00
LOCAL: Auditório do CI
TÍTULO: Algoritmos Exatos para o Problema da Edição de p-Clusters
PALAVRAS-CHAVES: Edição de Grafos; Clusterização; Branch-and-Cut; Branch-and-Price.
PÁGINAS: 82
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Matemática da Computação
RESUMO: Este trabalho trata do Problema de Edição de p-Clusters (p-PEC), o qual consiste em realizar um número mínimo de edições (adições ou remoções de arestas) em um grafo G de modo a transformá-lo em uma união disjunta de p cliques (ou clusters), sendo G e p dados de entrada. O p-PEC é um problema NP-Difícil que possui aplicações em áreas como biologia computacional e aprendizagem de máquina. Para resolvê-lo, foram propostas duas novas formulações matemáticas e melhorias em uma formulação proveniente da literatura, bem como novas desigualdades válidas. As três formulações consideradas foram estudadas tanto teoricamente, através da comparação entre as relaxações lineares, quanto empiricamente, através do desenvolvimento de três algoritmos exatos: dois baseados em Branch-and-Cut (BC) e um baseado em Branch-and-Price (BP). Os algoritmos foram testados em instâncias com até 211 vértices. Os resultados mostram o impacto da razão entre p e o número de vértices, da densidade do grafo e das desigualdades nos desempenhos dos algoritmos. No geral, os algoritmos BC foram superiores ao algoritmo BP. Porém, em algumas instâncias, os melhores limites duais foram obtidos pelo algoritmo BP.
MEMBROS DA BANCA:
Presidente - 1175878 - LUCIDIO DOS ANJOS FORMIGA CABRAL
Interno - 1859144 - ANAND SUBRAMANIAN
Interno - 337293 - ROBERTO QUIRINO DO NASCIMENTO
Externo à Instituição - MANOEL BEZERRA CAMPELO NETO