binary integer programming

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

  • Evren Güney
    • Categories 0-1 Programming, Approximation Algorithms, Network Optimization Tags , , ,

    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

  • Shabbir Ahmed
  • Fatma Kılınç-Karzan
  • George L. Nemhauser
  • Martin Savelsbergh
  • Alejandro Toriello
    • Categories 0-1 Programming Tags , ,

    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