CATS-Apr-4-2014
Title[edit]
Weighted and Fractional Versions of the Target Set Selection Problem on Trees
Speaker[edit]
Dr. Raghavan is passionate about using quantitative methods (in particular optimization models) for better decision making. His research interests and activities cover a broad domain including--- auction design, data mining, economics, information systems, computational marketing, networks, optimization, and telecommunications. He has published on a wide variety of topics (including telecommunications, electronic markets, and data mining) and numerous academic outlets such as Management Science, Operations Research, Decision Support Systems, and the INFORMS Journal on Computing. He holds two patents, and has won numerous awards for his work. These include (i) the Dantzig award for the best doctoral dissertation, (ii) the INFORMS Computing Society Prize (twice); once for innovative contributions to the field of data mining, and a second time for his contributions to public sector auction design, (iii) the Glover-Klingman Prize for the best paper in the journal Networks, (v) the Management Science Strategic Innovation Prize by the European Operations Research Society, (v) 2nd Prize in the INFORMS Junior Faculty Paper Competition, (vi) Finalist for the European Operations Research Society Excellence in Practice Award, and (vii) Finalist for the Wagner Prize for Excellence in Operations Research Practice. He has edited six books titled Telecommunications Network Design and Management (Kluwer Academic Press 2003), Telecommunications Planning: Innovations in Pricing, Network Design, and Management (Springer 2006), The Next Wave in Computing, Optimization, and Decision Technologies (Springer 2005), Telecommunications Modeling, Policy, and Technology (Springer 2008), The Vehicle Routing Problem: Latest Advances and New Challenges (Springer 2008), and Tutorials in Operations Research (INFORMS 2008). He enjoys teaching decision modeling oriented courses, and is a recipient of the Legg-Mason Teaching Innovation award at the Smith School. Prior to joining the Smith School he led the Optimization Group at U S WEST Advanced Technologies.
Abstract[edit]
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)
