SEAS Department Website

• Home

• Department Overview
• People
• Research
• Seminars & Groups
  • Financial Engineering Practitioners Seminars
  • IEOR-DRO Seminars
  • The New York Quantitative Finance Seminar
  • The Discrete Math Seminar
  • Financial Engineering Summer Informal Seminar
  • IEOR Seminars
• Admissions
• Undergraduate
• Graduate
• Industry Outreach
• Careers
• News & Events
• Resources

Seminars & Groups

Submodular Maximization applied to Marketing over Social Networks

Date: 02-24-2009
Start Time: 12:30pm
End Time: 1:30pm
Speaker: Vahab Mirrokni, Google
Location: Uris 333

ABSTRACT

Submodular maximization is a central problem in optimization with several applications. Unlike minimizing submodular functions, submodular maximizatin is NP-hard. In this talk, we first describe recent approximation algorithms for this problem, and then discuss an application in optimal marketing over social networks.  

We give the first constant-factor approximation algorithms for maximizing non-negative submodular functions with multiple budget and matroid constraints.  In particular, we give a randomized 2/5-approximation algorithm for maximizing non-negative submodular functions and a 1/5-approximatin for maximizing submodular functions with multiple budget constraints. Furthermore, we prove that achieving an approximation factor better than 1/2 requires exponential time.

In the second half of the talk, I will discuss an application in marketing digital goods over social networks, and study revenue-maximizing marketing strategies in the presence of positive network externalities of buyers. In particular, we study a set of influence-and-exploit marketing strategies and show how to use submodualr maximization to identify a set of influential buyers in a social network.

This talk is based on joint work with Feige and Vondrak (FOCS 2007), Hartline and Sundararajan (WWW 2008), and Lee, Nagarajan, Sviridenko (STOC 2009).

BIO

Vahab Mirrokni is a Senior Research Scientist at Google Research in New York. He joined Google after receiving a B.Sc. from Sharif University in 2001 and a Ph.D. from MIT in 2005,  one year at MIT and Amazon.com, and two years at Microsoft Research.  Vahab's main research interests are algorithmic game theory, approximation algorithms, and the Internet Economics.  He has published more than 55 papers in journals and conferences and has filed 12 patents in these areas. Vahab is co-winner of the SODA 2005 best student paper award and the ACM EC 2008 best paper award.