CATS-Apr-4-2014

Title

Weighted and Fractional Versions of the Target Set Selection Problem on Trees

Speaker

S. Raghu Raghavan, Professor of Management Science and Operations Management, University of Maryland

Abstract

The Target Set Selection (TSS) problem is a fundamental problem about the diffusion of influence in social networks that has been widely studied in the literature. The TSS problem has applications in many areas in economics, business, sociology and medicine including viral marketing and epidemiology. In this talk I will discuss 1) A weighted version of the TSS problem (WTSS problem). The weights in the WTSS problem model the fact the cost or effort to activate different nodes can vary. 2) A fractional version of the TSS problem. The fractional activation of a node has a natural interpretation as the payment of partial incentives to adopt a product in the viral marketing context. We call this fractional version of the TSS problem, the Least Cost Influence Problem (LCIP).

Both problems are NP-hard on general graphs. Motivated by the desire to develop mathematical programming approaches to solve these two problems, we focus on developing strong formulations for these problems on trees. In particular, we are interested in formulations whose linear programming relaxations are integral. Based on the observation that the influence propagation network is a directed acyclic graph, these integral formulations can be embedded into a larger exponential sized integer programming formulation for these two problems on general graphs. In the talk I will focus on simple dynamic programming algorithms for both problems, and developing integral formulations for both problems on trees. Time permitting I will describe results with a branch-and-cut approach to solve these problems on general graphs. (Joint work with Dilek Gunnec and Rui Zhang)

Web Accessibility