Bureaucrats, editor, Administrators
373
edits
Changes
→Speaker
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.
+
+
+== Abstract ==
+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