TY - GEN

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

AU - Bansal, Nikhil

AU - Gupta, Anupam

AU - Krishnaswamy, Ravishankar

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77951690098&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951690098&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973075.125

DO - 10.1137/1.9781611973075.125

M3 - Conference contribution

AN - SCOPUS:77951690098

SN - 9780898717013

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1539

EP - 1545

BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery (ACM)

T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 2010 through 19 January 2010

ER -