Name
Abstract | ||
|---|---|---|
Consider the problem of laying out a set of $n$ images that match a query onto the nodes of a $\sqrt{n}\times\sqrt{n}$ 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 \emph{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. This layout problem is prototypical in a number of applications in web search and advertising, particularly in an 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. We study 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 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 sub modular with two matroid constraints, which admits a constant-factor approximation. In contrast, we also show the problem is APX-hard via a reduction from {\sc Cubic Max-Bisection}. We then study harder variants of greater practical interest of the problem in which no \emph{gaps}--states of $M$ with no object placed on them--are allowed. By exploiting the geometry, we obtain an $O(\log^{3/2} n)$ approximation algorithm when the digraph underlying $M$ is a grid and an $O(\log n)$ approximation algorithm when it is a tree. These special cases are especially appropriate for our applications. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/FOCS.2011.71 | Foundations of Computer Science |
Keywords | DocType | ISSN |
Markov processes,Web sites,advertising,approximation theory,computational complexity,optimisation,probability,set theory,APX hard problem,Markov chain,Markov layout problem,Web page,Web search,advertising,constant factor approximation algorithm,cubic max bisection,logarithmic factor,matroid constraint,optimization problem,partial permutation,pattern distribution,publisher Website,stopping probability,markov chain,utility,webpage layout | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-4577-1843-4 | 1 | 0.36 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Flavio Chierichetti | 1 | 626 | 39.42 |
| Ravi Kumar | 2 | 13932 | 1642.48 |
| Prabhakar Raghavan | 3 | 13351 | 2776.61 |