Difference between revisions of "CATS-May-13-2013"

From Theory
Line 15: Line 15:
 
apply.
 
apply.
  
−
== Abstract ==
+
The first part of this talk focuses on a network diffusion model
−
Network routing games are instrumental in understanding
+
  that was recently introduced by Goldberg & Liu (SODA'13). Goldberg &
−
traffic patterns and improving congestion in networks. They have a
+
  Liu's model adapts the earlier linear threshold model of Kempe,
−
direct application in transportation and telecommunication networks
+
  Kleinberg & Tardos (KDD'03) in an effort to capture aspects of
−
and extend to many other applications such as task planning, etc.
+
  technology adaptation processes in networks. We present new,
−
Theoretically, network games were one of the central examples in the
+
  improved, yet simple algorithms for the so called Influence
−
development of algorithmic game theory.
+
  Maximization problem in this setting.
  
−
In these games, multiple users need to route between di fferent
+
  A key component of our algorithm is a Langrangean multiplier
−
source-destination pairs and links are congestible, namely, each link
+
  preserving (LMP) algorithm for the Prize-collecting Node-weighted
−
delay is a non-decreasing function of the flow on the link. Many of
+
  Steiner Tree problem (PC-NWST). This problem had been studied in
−
the fundamental game theoretic questions are now well understood for
+
  prior work by Moss and Rabani (STOC'01 & SICOMP'07) who presented a
−
these games, for example, does equilibrium exist, is it unique, can it
+
  primal-dual O(log |V|) approximate and LMP algorithm, and showed
−
be computed e fficiently, does
+
  that this is best possible unless NP=P.
−
it have a compact representation; the same questions can be asked of
 
−
the socially optimal solution that minimizes the total user delay.
 
  
−
So far, most research has focused on the classical models in which the
+
  We demonstrate that Moss & Rabani's algorithm for PC-NWST is
−
link delays are deterministic. In contrast, real world applications
+
  seriously flawed. We then present a new, fundamentally different
−
contain a lot of uncertainty, which may stem from exogenous factors
+
  primal-dual method achieving the same performance guarantee. Our
−
such as weather, time of day, weekday versus weekend, etc. or
+
  algorithm introduces several novel features to the primal-dual
−
endogenous factors such as the network tra ffic.  Furthermore, many
+
  method that may be of independent interest.
−
users are risk-averse in the presence of uncertainty, so that they do
 
−
not simply want to minimize expected delays and instead may need to
 
−
add a bu ffer to ensure a guaranteed arrival time to a destination.
 
  
−
I present my recent work on a new stochastic network game model with
+
  Joint work with Laura Sanita and Sina Sadeghian
−
risk-averse users.  Risk-aversion poses a computational challenge and
 
−
it often fundamentally alters the mathematical structure of the game
 
−
compared to its deterministic counterpart, requiring new tools for
 
−
analysis.  The talk will discuss best response and equilibrium
 
−
analysis, as well as equilibrium efficiency (price of anarchy) and a
 
−
new concept, the price of risk.
 
−
 
 
−
One relevant paper is here:
 
−
http://faculty.cse.tamu.edu/nikolova/papers/Stochastic-selfish-routing-full.pdf
 
−
 
 
−
A short summary of the paper is here:
 
−
http://www.sigecom.org/exchanges/volume_11/1/NIKOLOVA.pdf
 

Revision as of 20:14, 25 April 2013

Title[edit]

Network Diffusion & Node-Weighted Steiner Trees

Speaker[edit]

Evdokia Nikolova is an Assistant Professor at the Computer Science & Engineering Department at Texas A&M University. Previously she was a postdoctoral associate in the Computer Science and Artificial Intelligence Laboratory at MIT. She graduated with a BA in Applied Mathematics with Economics from Harvard University, MS in Mathematics from Cambridge University (U.K.) and Ph.D. in Computer Science from MIT. She is interested in risk analysis from an algorithmic perspective arising in stochastic optimization, networks, economics and complex systems. She has worked on applications to transportation and is also interested in energy and other domains where her work may 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

Web Accessibility

Retrieved from "https://wiki.cs.umd.edu/theory/w/index.php?title=CATS-May-13-2013&oldid=1687"