An Efficient Linear Programming Based Method for the Influence Maximization Problem in Social Networks

The influence maximization problem (IMP) aims to determine the most influential individuals within a social network. In this study first we develop a binary integer program that approximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently, we propose a linear programming relaxation based method with a provable worst case bound that … Read more

Approximating the Stability Region for Binary Mixed-Integer Programs

We consider optimization problems with some binary variables, where the objective function is linear in these variables. The stability region of a given solution of such a problem is the polyhedral set of objective coefficients for which the solution is optimal. A priori knowledge of this set provides valuable information for sensitivity analysis and re-optimization … Read more