NP-hardness and evolutionary algorithm over new formulation for a Target Set Selection problem

Author(s)

Ravelo, Santiago, V ; Meneses, Claudio N. ; Anacleto, Eduardo A. J. ; IEEE

• Document type: Journal article
• Source: 2020 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC); v. N/A, p. 8-pg., 2020-01-01.

Abstract

This work considers the Target Set Selection problem, which can be used to model the propagation and consumption of information, data, ideas and products through networks, with applications in marketing, medicine, sociology and bioinformatics. We propose a new version of the problem and prove it belongs to the NP-hard class. We also design an evolutionary algorithm that uses, in the crossover and mutation operators, exact solutions of sub-problems which were modeled by a new mathematical formulation. We test our approach over a benchmark of instances constructed from real-world data sets. (AU)

• FAPESP's process: 18/03819-4 - Methods for Solving Quadratic Binary Optimization Problems
• Grantee: Eduardo Alves de Jesus Anacleto
• Support Opportunities: Scholarships in Brazil - Doctorate