Min-Sum Set Cover on Parallel Machines

Consider the classical Min-Sum Set Cover problem: We are given a universe $\mathcal{U}$ of $n$ elements and a collection $\mathcal{S}$ of $k$ subsets of $\mathcal{U}$. Moreover, a cost function is associated with each set. The goal is to find a subsequence of sets in $\mathcal{S}$ that covers all elements in $\mathcal{U}$, such that the sum of the covering times of the elements is minimized. The covering time of an element $u$ is the cost of all sets that appear in the sequence before $u$ is first covered. This problem can be seen as a scheduling problem on a single machine, where each job represents a set and elements are represented by some kind of utility that is required to be provided by at least one of the jobs. The goal is to schedule the jobs in such a way to minimize the sum of provision times of the utilities. In this paper we consider a natural generalization of this problem to the case of $m$ machines, processing the jobs in parallel. We call this problem Parallel Min-Sum Set Cover. To obtain approximation algorithms for both related and unrelated machines, we use a crucial subproblem which we call Parallel Maximum Coverage. We give a randomized bicriteria $(1-1/e-\epsilon, O(\log m/\log\log m))$-approximation algorithm for this problem based on a natural LP relaxation. This can be then used to obtain $O(\log m/\log\log m)$-approximation algorithm for the Min-Sum Set Cover problem on unrelated machines. For related machines, we allow the aforementioned bicriteria approximation algorithm to run in FPT time, and apply a technique enabling transformation of a related machines instance into one consisting of $O(\log m)$ unrelated machines, to get an $\frac{8e}{e+1}+\epsilon <12.66$-approximation algorithm for this case. We also show a greedy algorithm for unit cost sets, subject to precedence constraints, with an $O(k^{2/3})$ approximation ratio.