Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
→Abstract
== Abstract ==
== Abstract ==
The first part of this talk focuses on a network diffusion model
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
