Exact algorithms and heuristics for the Perfect Awareness problem

• Grant number: 19/22297-1
• Support Opportunities: Scholarships in Brazil - Master
• Start date: July 01, 2020
• End date: February 28, 2021
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Pedro Jussieu de Rezende
• Grantee: Felipe de Carvalho Pereira
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

We present a research proposal to be developed during the Master's Program in Computer Science at the Institute of Computing of the University of Campinas. The research topic involves the study of an NP-hard combinatorial optimization problem called perfect awareness. In this problem, we consider a social network in which information is propagated between connected individuals. The goal is to select a smallest possible initial set of disseminators so that by the end of the propagation process all individuals are aware of the information.This proposal contextualizes the problem, presents a formal definition and a literature review. We also describe a work methodology that aims to solve the problem through heuristic algorithms based on the GRASP metaheuristic and through exact algorithms via integer linear programming. This document also lists the objectives of the work, the preliminary and expected results, and a schedule of activities.An initial set of experiments has been performed and the results look quite promising considering that one of the heuristics we implemented surpassed the only algorithm proposed in the literature for this problem so far. Given this, the main objective of this work is to develop new algorithms to solve the perfect awareness problem and to undertake computational experiments so that the results so obtained can be compared with the best known algorithms for the problem. (AU)

Scientific publications

(The scientific publications listed on this page originate from the Web of Science or SciELO databases. Their authors have cited FAPESP grant or fellowship project numbers awarded to Principal Investigators or Fellowship Recipients, whether or not they are among the authors. This information is collected automatically and retrieved directly from those bibliometric databases.)

PEREIRA, FELIPE DE C.; DE REZENDE, PEDRO J.; DE SOUZA, CID C.; FERREIRA, CE; LEE, O; MIYAZAWA, FK. Effective Heuristics for the Perfect Awareness Problem. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 10-pg., 2021-01-01. (14/12236-1, 19/22297-1, 18/26434-0)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

PEREIRA, Felipe de Carvalho. A computational study of the Perfect Awareness Problem. 2021. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.