Approximating Min-Sum Set Multicover

Question

Approximations for the set multicover problem have been studied (Rajagopalan & Vazirani (section 5)), as have approximations for the min-sum set cover problem (Feige et al.). 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!

Answer 1

Yes, this has been studied. It was called the multiple intents re-ranking problem by Azar, Gamzu, and Yin 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 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 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.