Approximating Generalized Min Sum Set Cover

Anupam Gupta
Department of Computer Science
Carnegie Mellon University


Wednesday, March 3, 2010
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:

Consider the following variant of the set-cover problem: There is a universe of elements and a collection of sets, with each set S also having an associated covering requirement of K(S). The goal is to output an ordering of the elements such that the total "cover time" of all the sets is minimized, where the cover time of a set is the first time when K(S) elements from S have been output.

The problem was introduced by Azar, Gamzu, and Yin (STOC 09) as a theoretical modeling of a web-search ranking problem, where the requirement is to compute an ordering of web-pages for a given search query such that the average user finds the page(s) he/she is looking for quickly; they also gave a logarithmic approximation algorithm. In this talk, we give a simple randomized constant factor approximation algorithm for this problem, based on a strengthened linear program relaxation.

This is joint work with Nikhil Bansal and Ravishankar Krishnaswamy, and appeared at the SODA 2010 conference.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html