Online Allocations and Advertising

ABSTRACT:
Matching and Assignment problems are among the most basic and important 
questions in Computer Science; celebrated algorithms such as the Hungarian 
method and Edmonds' blossom algorithm were among the early successes of 
combinatorial optimization. These, and more general problems of allocating 
goods to agents, find a number of applications ranging from Economics to 
scheduling to inventory management.

In several settings, however, such problems must be solved without knowing 
the entire input in advance; these are online allocation problems. In some 
applications, one has a known or fixed inventory of goods, and agents 
appear online to bid for subsets of these goods. In other problems, the 
set of agents is known in advance, and as goods appear or are produced, 
they must be allocated to agents. In this talk, I will present simple and 
effective algorithms for several online allocation problems, motivated by 
applications to Internet and traditional media advertising.

BIO:
Nitish Korula is a Ph.D. candidate in Computer Science at the University 
of Illinois, Urbana-Champaign, where he is the most recent recipient of 
the University of Illinois Dissertation Completion Fellowship.
He completed his B.E. at Birla Institute of Technology & Science, Pilani, 
India. His research is primarily on effective algorithms for optimization 
problems; particular interests are the fields of approximation and online 
algorithms, and graph theory.