University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Jochen KonemannExport this event to calendar

Friday, May 24, 2013 — 3:30 PM to 4:30 PM EDT

Network Diffusion and Node-Weighted Steiner Trees

Speaker: Jochen koenemann
Affiliation: University of Waterloo
Room: Mathematics and Computer Building (MC) 5158

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 was studied in prior work by Moss and Rabani (STOC'01 & SICOMP'07) who gave a primal-dual O(log |V|) approximate and LMP algorithm, and showed that this is best possible unless NP=P.

We show that Moss & Rabani's algorithm for PC-NWST has a serious flaw. 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

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2021 (45)
    1. May (5)
    2. April (9)
    3. March (13)
    4. February (8)
    5. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)