A Cutting Plane Method for Least Cost Influence Maximization

摘要

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.