A constant factor approximation algorithm for generalized min-sum set cover

Abstract

Consider the following generalized min-sum set cover or multiple intents re-ranking problem proposed by Azar et al. (STOC 2009). We are 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: (i) when K(S) = 1 for all sets, we get the min-sum set cover problem, and (ii) when K(S) = |S| for all sets, we get the minimum-latency set cover problem. Constant factor approximations are known for both these problems. In their paper, Azar et al. considered the general problem and gave a logarithmic approximation algorithm for it. In this paper, we improve their result and give a simple randomized constant factor approximation algorithm for the generalized min-sum set cover problem. Copyright © by SIAM.