Bureaucrats, editor, Administrators
373
edits
Changes
→Abstract
Line 18:
Line 18:
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+
== 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