DEPARTMENT SEMINAR

Vahab Mirrokni Microsoft Research Theory Group

Monday, April 7, 2008 Computer Science Building, Room 151 4:00 PM

Faculty Host:Ramesh Sitaraman

"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 more than 50 papers and has filed more
than 10 patents.

Refreshments at 3:40 PM in the atrium, outside the presentation room.