| 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
| |
