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

N. Bansal, A. Gupta, R. Krishnaswamy

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

33 Citations (Scopus)
1 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10, Austin TX, USA, January 17-19, 2010)
EditorsM. Charikar
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages1539-1545
ISBN (Print)978-0-898717-01-3
Publication statusPublished - 2010
Externally publishedYes

Publication series

NameProceedings in Applied Mathematics
Volume135

Fingerprint

Dive into the research topics of 'A constant factor approximation algorithm for generalized min-sum set cover'. Together they form a unique fingerprint.

Cite this