Bureaucrats, editor, Administrators
373
edits
Changes
→Speaker
Line 14:
Line 14:
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
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.
−