| Full text | |
| Author(s): |
Renato Silva de Melo
[1]
;
André Luís Vignatti
[2]
;
Flávio Keidi Miyazawa
[3]
;
Matheus Jun Ota
[4]
Total Authors: 4
|
| Affiliation: | [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
Total Affiliations: 4
|
| Document type: | Journal article |
| Source: | Pesquisa Operacional; v. 43, 2023-11-10. |
| Abstract | |
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) | |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |