A Cutting Plane Method for Least Cost Influence Maximization.
Published in Computational Data and Social Networks - 9th International Conference, CSoNet 2020, Dallas, TX, 2021
Abstract: We study the least cost influence maximization problem, which has potential applications in social network analysis, as well as in other types of networks. The focus of this paper is on mixed-integer programming (MIP) techniques for the considered problem. The standard arc-based MIP formulation contains a substructure that is a relaxation of the mixed 0-1 knapsack polyhedron. We give a new exponential class of facet-defining inequalities from this substructure and an exact polynomial time separation algorithm for the inequalities. We report preliminary computational results to illustrate the effect of these inequalities.
Citation: Chen, C. L., Pasiliao, E. L., & Boginski, V. (2020, December). A Cutting Plane Method for Least Cost Influence Maximization. In International Conference on Computational Data and Social Networks (pp. 499-511).