Approximating Generalized Min Sum Set Cover
Nov 4, 2009
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 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 will go over a simple randomized constant factor approximation algorithm for this problem.
(joint work with Nikhil Bansal and Anupam Gupta)
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.