@inproceedings{ff0437a3a6854a129ff3fb4683c66997,

title = "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.",

author = "N. Bansal and A. Gupta and R. Krishnaswamy",

year = "2010",

language = "English",

isbn = "978-0-898717-01-3",

series = "Proceedings in Applied Mathematics",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

pages = "1539--1545",

editor = "M. Charikar",

booktitle = "Proceedings 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10, Austin TX, USA, January 17-19, 2010)",

address = "United States",

}