NDLI: Markov Layout

Content Provider	IEEE Xplore Digital Library
Author	Chierichetti, F. Kumar, R. Raghavan, P.
Copyright Year	2011
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.
Starting Page	492
Ending Page	501
File Size	664560
Page Count	10
File Format	PDF
ISBN	9781457718434
ISSN	02725428
e-ISBN	9780769545714
DOI	10.1109/FOCS.2011.71
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-10-22
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Markov processes Approximation methods Layout Approximation algorithms Web pages Search problems Optimization utility webpage layout markov chain
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Libarray of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

WNPWR: Web navigation prediction framework for webpage recommendation

Study of a Layout Optimization Problem of Web Advertising

Reinforcement learning for the unit commitment problem

Hybridization of K-Means and Harmony Search Methods for Web Page Clustering

Web page clustering using Harmony Search optimization

Sensor control for search and identification of Markov objects

A Web Mining Model for Real-time Webpage Personalization

Distributed Optimization for Combinatorial Coding Subgraph Selection Problems

A survey: hyperlink analysis in webpage ranking algorithms

Markov Layout

Similar Documents

WNPWR: Web navigation prediction framework for webpage recommendation

Study of a Layout Optimization Problem of Web Advertising

Reinforcement learning for the unit commitment problem

Hybridization of K-Means and Harmony Search Methods for Web Page Clustering

Web page clustering using Harmony Search optimization

Sensor control for search and identification of Markov objects

A Web Mining Model for Real-time Webpage Personalization

Distributed Optimization for Combinatorial Coding Subgraph Selection Problems

A survey: hyperlink analysis in webpage ranking algorithms

Markov Layout