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

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: 2020 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC); v. N/A, p. 8-pg., 2020-01-01.

Resumo

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)

• Processo FAPESP: 18/03819-4 - Métodos para Resolução de Problemas de Otimização Quadráticos Binários
• Beneficiário: Eduardo Alves de Jesus Anacleto
• Modalidade de apoio: Bolsas no Brasil - Doutorado