CS Faculty Candidate Colloquium
Monday **Special Time & Location** March 31 10:45 - 11:50 AM Kelley 1007 Vahab Mirrokni EECS Colloquium: Computer Science Faculty Candidate Postdoctoral Researcher in the Theory Group Microsoft 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). Biography 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.
_______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
