| Texto completo | |
| Autor(es): |
Renato Silva de Melo
[1]
;
André Luís Vignatti
[2]
;
Flávio Keidi Miyazawa
[3]
;
Matheus Jun Ota
[4]
Número total de Autores: 4
|
| Afiliação do(s) autor(es): | [1] Federal University of Paraná. Department of Computer Science - Brasil
[2] Federal University of Paraná. Department of Computer Science - Brasil
[3] University of Campinas. Institute of Computing - Brasil
[4] University of Campinas. Institute of Computing - Brasil
Número total de Afiliações: 4
|
| Tipo de documento: | Artigo Científico |
| Fonte: | Pesquisa Operacional; v. 43, 2023-11-10. |
| Resumo | |
ABSTRACT The Least Cost Influence Problem is a combinatorial optimization problem that appears in the context of social networks. The objective is to give incentives to individuals of a network, such that some information spreads to a desired fraction of the network at minimum cost. We introduce a problem-dependent algorithm in a branch-and-bound scheme to compute a dual bound for this problem. The idea is to exploit the connectivity properties of sub-graphs of the input graph associated with each node of the branch-and-bound tree and use it to increase each sub-problem’s lower bound. Our algorithm works well and finds a lower bound tighter than the LP-relaxation in linear time in the size of the graph. Computational experiments with synthetic graphs and real-world social networks show improvements in using our proposed bounds. The improvements are gains in running time or gap reduction for exact solutions to the problem. (AU) | |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |