Eastern Great Lakes Theory Workshop Talk

Markov Layout

Flavio Chierichetti, Cornell University

Saturday, September 10, 2:30-3:30pm

ABSTRACT

Consider the following problem of laying out a set of n images that match a query onto the nodes of a n^0.5 X n^0.5 grid. We are given a score for each image, as well as the distribution of patterns by which a user's eye scans the nodes of the grid and we wish to maximize the expected total score of images selected by the user. This is a special case of the Markov layout problem, in which we are given a Markov chain M together with a set of objects to be placed at the states of the Markov chain. Each object has a utility to the user if viewed, as well as a stopping probability with which the user ceases to look further at objects. We point out that this layout problem is prototypical in a number of applications in web search and advertising, particularly in the emerging genre of search results pages from major engines. In a different class of applications, the states of the Markov chain are web pages at a publishers website and the objects are advertisements.

In this talk, we will present results on the approximability of the Markov layout problem. Our main result is an O(log n) approximation algorithm for the most general version of the problem. The core idea behind the algorithm is to transform an optimization problem over partial permutations into an optimization problem over sets by losing a logarithmic factor in approximation; the latter problem is then shown to be submodular with two matroid constraints, which admits a constant-factor approximation.

We then study variants of the problem in which no gaps --- states of M with no object placed on them --- are allowed, and in which we put restrictions on the structure of the Markov chain.

Speaker Bio

Flavio Chierichetti is a postdoctoral researcher in the Department of Computer Science at Cornell University. He has received his Ph.D. in Computer Science from Sapienza University of Rome in 2010. His main research interests lie in probabilistic models and algorithmics in the contexts of social networks and the web.

< Schedule < EaGL-IV homepage