<p>Yes, this has been studied. It was called the multiple intents re-ranking problem by <a href="http://research.microsoft.com/pubs/117900/stoc09_reranking.pdf" rel="nofollow">Azar, Gamzu, and Yin</a> who gave a $\log n$ approximation using a cleverly modified greedy algorithm (the point is being greedy with respect to a clever metric). <a href="http://www.win.tue.nl/~nikhil/pubs/gen-mssc.pdf" rel="nofollow">Bansal, Gupta, and Krishnaswamy</a> had the good sense to rename the problem to generalized min-sum set cover and gave a constant approximation via LP rounding. The constant is very large, more than 400. <a href="http://www.sciencedirect.com/science/article/pii/S0167637711000885" rel="nofollow">Skutella and Williamson</a> improved this to 28.</p>

<p>BTW you state the problem as finding an ordering on the sets to satisfy a coverage requirement on the elements. Some of the above papers state the problem in the equivalent dual form: find an ordering on the elements to satisfy hitting requirements on the sets. </p>

CC BY-SA 3.0
2013-06-28T01:53:59.470Z
2013-06-28T03:53:45.520Z
2013-06-28T03:53:45.520Z
Sasho Nikolov
<p>Approximations for the set multicover problem have been studied (<a href="http://www.cc.gatech.edu/~mihail/D.read2010/Rajagopalan_Vazirani.pdf" rel="nofollow">Rajagopalan &amp; Vazirani (section 5)</a>), as have approximations for the min-sum set cover problem (<a href="http://link.springer.com/chapter/10.1007%2F3-540-45753-4_10" rel="nofollow">Feige et al.</a>). The greedy heuristic gives a $\log(n)$-approximation for the set multicover problem and a 4-approximation for min-sum set cover.</p>

<p>Consider the min-sum set multicover problem, i.e. for each ground element $e_i$ with coverage requirement $r_i$, let $f(e_i)$ be the step in which the coverage requirement is met; we then wish to minimize $\textstyle\sum_{i=1}^n f(e_i)$.</p>

<p>By extending the 4-approximation in Feige et al., it is trivial to get a $4r$-approximation for min-sum set multicover, where $r=\max r_i$. It is most likely that a better approximation ratio can be achieved.</p>

<p>Does anyone know of any work that has been done on the min-sum set multicover problem? Any pointers to other names for the problem would also be very helpful. Thanks in advance!</p>

<reference-request><approximation-algorithms><set-cover>
Approximating Min-Sum Set Multicover
plin25
# Approximating Min-Sum Set Multicover

(Asked by: username_0 on 2013-06-28)

Approximations for the set multicover problem have been studied ([Rajagopalan & Vazirani (section 5)](http://www.cc.gatech.edu/~mihail/D.read2010/Rajagopalan_Vazirani.pdf)), as have approximations for the min-sum set cover problem ([Feige et al.](http://link.springer.com/chapter/10.1007%2F3-540-45753-4_10)). The greedy heuristic gives a $\log(n)$-approximation for the set multicover problem and a 4-approximation for min-sum set cover.

Consider the min-sum set multicover problem, i.e. for each ground element $e\_i$ with coverage requirement $r\_i$, let $f(e\_i)$ be the step in which the coverage requirement is met; we then wish to minimize $\textstyle\sum\_{i=1}^n f(e\_i)$.

By extending the 4-approximation in Feige et al., it is trivial to get a $4r$-approximation for min-sum set multicover, where $r=\max r\_i$. It is most likely that a better approximation ratio can be achieved.

Does anyone know of any work that has been done on the min-sum set multicover problem? Any pointers to other names for the problem would also be very helpful. Thanks in advance!

**Tags:** reference-request, approximation-algorithms, set-cover


---

## 1 answers

### Answer by username_1 on 2013-06-28. Score: 5 | Accepted answer

Yes, this has been studied. It was called the multiple intents re-ranking problem by [Azar, Gamzu, and Yin](http://research.microsoft.com/pubs/117900/stoc09_reranking.pdf) who gave a $\log n$ approximation using a cleverly modified greedy algorithm (the point is being greedy with respect to a clever metric). [Bansal, Gupta, and Krishnaswamy](http://www.win.tue.nl/~nikhil/pubs/gen-mssc.pdf) had the good sense to rename the problem to generalized min-sum set cover and gave a constant approximation via LP rounding. The constant is very large, more than 400. [Skutella and Williamson](http://www.sciencedirect.com/science/article/pii/S0167637711000885) improved this to 28.

BTW you state the problem as finding an ordering on the sets to satisfy a coverage requirement on the elements. Some of the above papers state the problem in the equivalent dual form: find an ordering on the elements to satisfy hitting requirements on the sets.


---

