Advanced search
Start date
Betweenand

Exact algorithms and heuristics for the Perfect Awareness problem

Grant number: 19/22297-1
Support type:Scholarships in Brazil - Master
Effective date (Start): July 01, 2020
Effective date (End): February 28, 2021
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Pedro Jussieu de Rezende
Grantee:Felipe de Carvalho Pereira
Home 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)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)