Algoritmos exatos para o problema de edição de p-Clusters
2015
Este trabalho trata do Problema de Edi¸c˜ao de p-Clusters (p-PEC), o qual consiste em
realizar um n´umero m´inimo de edi¸c˜oes (adi¸c˜oes ou remo¸c˜oes de arestas) em um grafo G
de modo a transform´a-lo em uma uni˜ao disjunta de p cliques (ou clusters), sendo G e p
dados de entrada. O p-PEC ´e um problema NP-Dif´icil que possui aplica¸c˜oes em ´areas
como biologia computacional e aprendizagem de m´aquina. Para resolvˆe-lo, foram propostas
duas novas formula¸c˜oes matem´aticas e melhorias em uma formula¸c˜ao proveniente da
literatura, bem como novas desigualdades v´alidas. As trˆes formula¸c˜oes consideradas foram
estudadas tanto teoricamente, atrav´es da compara¸c˜ao entre as relaxa¸c˜oes lineares, quanto
empiricamente, atrav´es do desenvolvimento de trˆes algoritmos exatos: dois baseados em
Branch-and-Cut (BC) e um baseado em Branch-and-Price (BP). Os algoritmos foram testados
em instˆancias com at´e 211 v´ertices. Os resultados mostram o impacto da raz˜ao entre
p e o n´umero de v´ertices, da densidade do grafo e das desigualdades nos desempenhos dos
algoritmos. No geral, os algoritmos BC foram superiores ao algoritmo BP. Por´em, em
algumas instˆancias, os melhores limites duais foram obtidos pelo algoritmo BP.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI