A Computational Study of the Perfect Awareness Problem - Pereira, Felipe de C.; Rezende, Pedro J. de; Souza, Cid C. de (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2022: Anais do XXXV Concurso de Teses e Dissertações, 2022)
The Perfect Awareness Problem (PAP) is a combinatorial optimization problem that models the spreading of information in social networks. The objective is to find a smallest subset of individuals that are able to start a viral propagation whereby a given news reaches everyone on a network, under certain dissemination restrictions. Considering that PAP is NP-hard, we present four novel heuristics based on the metaheuristic GRASP and show that the best one of our methods outperforms the only previously known heuristic designed for the problem. Our contributions also include: (i) a new publicly available benchmark of 840 instances that simulate social network relations, (ii) procedures for preprocessing instances, and (iii) two integer programming models to generate exact solutions for PAP. We conducted an exhaustive set of comparative experiments, followed by statistical analyses, showing the efficacy and efficiency of our algorithms.