A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover

Consider the following generalized min-sum set cover or multiple intents re-ranking problem proposed by Azar et al. (STOC 2009). The author is given a universe of elements and a collection of subsets, with each set S having a covering requirement of K(S). The objective is to pick one element at a time such that the average covering time of the sets is minimized, where the covering time of a set S is the first time at which K(S) elements from it have been selected. There are two well-studied extreme cases of this problem: when K(S) = 1 for all sets, one gets the min-sum set cover problem, and when K(S) = |S| for all sets, one gets the minimum-latency set cover problem.