16 dez 2024
14:00 Doctoral defense fully remotely
Theme
Exact Algorithms and Heuristics for Optimization Problems on the Spread of Information on Social Networks
Student
Felipe de Carvalho Pereira
Advisor / Teacher
Pedro Jussieu de Rezende - Co-supervisor: Tallys Hoover Yunes
Brief summary
Influence propagation in social networks has been studied as combinatorial optimization problems since the beginning of the 21st century and plays a significant role in the context of viral marketing. In this dissertation, we investigate three NP-hard optimization problems related to information propagation in social networks, in which we seek to identify influential individuals capable of inducing a wide-reaching chain of information diffusion while minimizing the costs associated with recruiting these influencers. Although these problems share important characteristics -- they can be described as graph problems in which individuals are represented by vertices and information flows through edges -- they differ in the way information spreads and in the constraints imposed on the selection of propagators. For the Least Cost Directed Perfect Awareness Problem, we present theoretical results on the difficulty of the problem, along with four integer programming formulations, three constraint programming models, and a heuristic based on the GRASP metaheuristic. To address Weighted Target Set Selection, we propose a hybrid multistage mathematic approach that integrates a preprocessing method with linear and integer programming techniques and a large neighborhood search procedure. Finally, to solve the Graph Burning Problem, we introduce an exact algorithm that finds optimal solutions through a binary search over the solution space, solving multiple decision problems in the form of mathematical models. For all these problems, we perform computational experiments with a variety of instances, demonstrating the efficiency and effectiveness of the proposed methods.
Examination Board
Headlines:
| Pedro Jussieu de Rezende | IC / UNICAMP |
| Breno Piva Ribeiro | DCOMP/UFS |
| Fábio Protti | IC / UFF |
| Kelly Cristina Poldi | IMECC / UNICAMP |
| Santiago Valdés Ravelo | IC / UNICAMP |
Substitutes:
| Ruben Interian Kovaliova | IC / UNICAMP |
| Carla Negri Lintzmayer | CMCC / UFABC |
| Mário César San Felice | DC / UFSCar |
| Hugo Kooki Kasuya Rosado | TUM/Germany |