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