Algoritmos exatos e heurísticos para o problema Perfect Awareness

Resumo

Apresentamos uma proposta de pesquisa a ser desenvolvida durante o curso de mestrado em Ciência da Computação do Instituto de Computação da Unicamp. O tópico de pesquisa envolve o estudo de um problema de otimização combinatória NP-difícil denominado perfect awareness. Neste problema, considera-se uma rede social na qual uma informação é propagada entre indivíduos conectados. O objetivo é selecionar um conjunto inicial de disseminadores de menor tamanho possível, de modo que, ao fim do processo de propagação, todos os indivíduos sejam conhecedores da informação. Esta proposta traz uma contextualização do problema, assim como sua definição formal e uma revisão bibliográfica. É descrita ainda uma metodologia de trabalho que visa solucionar o problema através de algoritmos heurísticos baseados na meta-heurística GRASP e por meio de algoritmos exatos via programação linear inteira. Neste documento, também são elencados os objetivos do trabalho, os resultados preliminares e os esperados, e um cronograma de atividades.Um conjunto de experimentos inicial foi realizado e os resultados mostraram-se promissores, uma vez que uma das heurísticas implementadas superou o único algoritmo proposto na literatura para o problema até o momento. Diante disso, o principal objetivo deste trabalho é desenvolver novos algoritmos para resolver o problema perfect awareness e submetê-los a experimentos computacionais para que os resultados obtidos sejam comparados com os melhores algoritmos conhecidos para o problema. (AU)