Fall 2011 Seminar Series

DATE: September 22nd
LOCATION: E62-550
TIME: 4:15pm
Reception immediately following

SPEAKER:
Amin Saberi

TITLE
From Online Matching to Online Advertising

ABSTRACT
I will talk about a simple graph problem: We are given a bipartite graph indicating potential matches between a set of boys and girls. The vertices corresponding to the boys arrive in a certain order and our task is to decide, as each boy vertex arrives, which girl vertex to match him to, so that the size of the matching obtained is maximized. Because of the simplicity of the problem, the central role of matching algorithms in combinatorial optimization, and recent applications in online advertising, this problem has received a lot of attention. In particular, several algorithms are developed for different variations in which the order of the boys is decided by a stochastic process or by an adversary. I will survey some of these results and explain their applications in online advertising.