Difference between revisions of "CATS-May-13-2013"

From Theory
Line 14: Line 14:
 
and is also interested in energy and other domains where her work may
 
and is also interested in energy and other domains where her work may
 
apply.
 
apply.
 
The first part of this talk focuses on a network diffusion model
 
  that was recently introduced by Goldberg & Liu (SODA'13). Goldberg &
 
  Liu's model adapts the earlier linear threshold model of Kempe,
 
  Kleinberg & Tardos (KDD'03) in an effort to capture aspects of
 
  technology adaptation processes in networks. We present new,
 
  improved, yet simple algorithms for the so called Influence
 
  Maximization problem in this setting.
 
 
  A key component of our algorithm is a Langrangean multiplier
 
  preserving (LMP) algorithm for the Prize-collecting Node-weighted
 
  Steiner Tree problem (PC-NWST). This problem had been studied in
 
  prior work by Moss and Rabani (STOC'01 & SICOMP'07) who presented a
 
  primal-dual O(log |V|) approximate and LMP algorithm, and showed
 
  that this is best possible unless NP=P.
 
 
  We demonstrate that Moss & Rabani's algorithm for PC-NWST is
 
  seriously flawed. We then present a new, fundamentally different
 
  primal-dual method achieving the same performance guarantee. Our
 
  algorithm introduces several novel features to the primal-dual
 
  method that may be of independent interest.
 
 
  Joint work with Laura Sanita and Sina Sadeghian
 

Revision as of 20:14, 25 April 2013

Title[edit]

Network Diffusion & Node-Weighted Steiner Trees

Speaker[edit]

Evdokia Nikolova is an Assistant Professor at the Computer Science & Engineering Department at Texas A&M University. Previously she was a postdoctoral associate in the Computer Science and Artificial Intelligence Laboratory at MIT. She graduated with a BA in Applied Mathematics with Economics from Harvard University, MS in Mathematics from Cambridge University (U.K.) and Ph.D. in Computer Science from MIT. She is interested in risk analysis from an algorithmic perspective arising in stochastic optimization, networks, economics and complex systems. She has worked on applications to transportation and is also interested in energy and other domains where her work may apply.