Abstract

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).



Information: