Min-Sum Set Cover on Parallel Machines

Abstract

We consider a generalization of the Min-Sum Set Cover to the setup with $m$ set-sequences, or in scheduling terminology, $m$ parallel machines. We call this problem Parallel Min-Sum Set Cover. To obtain approximation algorithms for its numerous variants we use a crucial sub-problem called Parallel Densest Subfamily. We prove that an $\alpha$-approximation algorithm for this task gives a $4\cdot \alpha$-approximation for the Parallel Min-Sum Set Cover, which yields $\frac{4\cdot e}{e-1}+\epsilon$ and $4\cdot {\frac{e}{e-1}}^2+\epsilon$-approximation ratios for identical and unrelated machines, respectively. To obtain the latter result we give a new ${\frac{e}{e-1}}^2+\epsilon$-approximation algorithm for the Maximum Coverage Multiple Knapsacks problem which is of independent interest. If the sets are precedence-constrained, for unit cost sets we give an $\mathcal{O}(k^{2/3})$ approximation ($k$ is the number of sets). For the case of out-forest precedence constraints we improve this bound to $\mathcal{O}(\log k)$ via a reduction to the Group Steiner Orienteering problem, and show this is tight, unless $NP\subseteq ZTIME(n^{\mathcal{O}(\text{poly}(\log n))})$.

arXiv comment19 pages