[Colloquium] Vahab Mirrokni (Theory Group, Microsoft Research)- TTI-C Talk

[Julia MacGlashan]

When:    Thursday, May 8 @ 10:00am

Where:   TTI-C Conference Room, 1427 E. 60th St.

Who:     Vahab Mirrokni (Theory Group, Microsoft Research)

Topic:   Online Advertisement and Submodular Maximization


Submodular maximization is a central problem in optimization with many
applications in data mining, social network analysis, and online
advertisement.  Unlike the problem of minimizing submodular functions, the
problem of maximizing submodular functions is NP-hard.

We design the first constant-factor approximation algorithms for maximizing
Non-negative submodular functions.
In particular, we give a deterministic local search 1/3-approximation and a
randomized 2/5-approximation algorithm for maximizing non-negative
submodular functions. Furthermore, we prove that achieving an approximation
factor better than 1/2 requires  exponential time.

Then, I will discuss applications of submodular maximization in the growing
field of the online advertisement, and in particular two specific
applications in marketing digital goods over social networks, and revenue
maximization for guaranteed banner advertisement. The first application is
concerned with viral marketing and word-of-mouth advertising in social
networks.
The second application is related to the banner ad allocation problem
satisfying a guaranteed delivery property.

The main part of the talk is based on joint work with Feige and Vondrak
(FOCS 2007), Hartline and Sundararajan (WWW 2008), and Feige, Immorlica, and
Nazerzadeh (WWW 2008).

Bio: Vahab Mirrokni is a Postdoctoral Researcher in the Theory Group at
Microsoft Research. He received his PhD from Massachusetts Institute of
Technology and his B.Sc. from Sharif University of Technology.
During his PhD studies, he spent some time doing research at IBM Research,
Bell-Laboratories, Microsoft Research, and Amazon.com.
His research areas include algorithmic game theory, approximation
algorithms, and social network analysis.
Recently at Microsoft Research, he has been working on various algorithmic
and economic problems related to the Internet search and online
advertisement.  He has published over 50 papers and has filed more than 10
patents.

Contact:     Julia Chuzhoy, TTI-C     cjulia at tti-c.org     834-2490