1 Introduction↩︎

Consider the following scenario: A massive infrastructure such as a network of bus stops is required to be built over the course of an extended period of time. The goal of the project is to provide all citizens with access to the public transportation. To do so, it is required to build the stops in such a way to enable each citizen to reach at least one of them within a reasonable time. Each such possible stop localization covers a certain subset of citizens which live nearby. The contractor appointed to carry out this task has multiple teams of workers at their disposal, each of which can build a single stop at a time. Moreover, the time required to build a stop at a given location may differ both between locations and teams. The goal of the contractor is to schedule the work of the teams in such a way that the average time required for a citizen to get access to the public transportation is minimized. This problem can be seen as a generalization of the classical Min-Sum Set Cover problem, which is defined as follows: 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 each element represents 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 as to minimize the sum of provision times of the utilities. In this work we consider a generalization of this problem to the case of \(m\) machines, processing the jobs in parallel. Figure 1 depicts an example problem instance and a feasible schedule on 3 machines.

1.1 Our results↩︎

We present a series of approximation algorithms for the Min-Sum Set Cover (PMSSC) problem on parallel machines. The most important part of our analysis is the choice of an appropriate subproblem, which we call the Parallel Densest Subfamily. In Section 3, we show how to use an \(\alpha\)-approximation algorithm for the Parallel Densest Subfamily to obtain a \(4/\alpha\)-approximation algorithm for the Min-Sum Set Cover problem on parallel machines. Our algorithm behaves greedily with respect to the found dense subfamily and its analysis is a variation on a particularly elegant analysis of the greedy algorithm for the Min-Sum Set Cover problem on a single machine used, among others, by Feige et. al. [1]–[3].

Then, in Section 4, we show how to solve Parallel Densest Subfamily for identical, related and unrelated machines. For the case of identical machines we use the \(\mathopen{}\left( 1-1/e \right)\)-approximation algorithm for the Maximum Coverage problem to obtain an \(\frac{e-1}{2e+\epsilon\cdot \mathopen{}\left( e-1 \right)}>0.32\)-approximation algorithm for the Parallel Densest Subfamily. For related machines we use a technique which shrinks the number of machines to \(O\mathopen{}\left( \log m \right)\), and then we use a bicriteria \(\mathopen{}\left( (1-1/e)\cdot(1-\epsilon), 1+\mu \right)\)-approximation algorithm for the problem called Parallel Maximum Coverage (PMC), running in time FPT in \(m\) to also get an \(\frac{e-1}{2e+\epsilon\cdot \mathopen{}\left( e-1 \right)}>0.32\)-approximation for related machines. For the case of unrelated machines we give an \(\Omega \mathopen{}\left( \log \log m/\log m \right)\)-approximation algorithm based on a similar, but polynomial time \(\mathopen{}\left( (1-1/e)\cdot(1-\epsilon), O\mathopen{}\left( \log m/\log\log m \right) \right)\)-approximation algorithm for the PMC.

In Section 5, we present both the aforementioned \(\mathopen{}\left( (1-1/e)\cdot(1-\epsilon), 1+\mu \right)\)-approximation FPT algorithm as well as poly-time \(\mathopen{}\left( (1-1/e)\cdot(1-\epsilon), O\mathopen{}\left( \log m/\log\log m \right) \right)\)-approximation algorithm for PMC based on a natural LP relaxation and a randomized rounding scheme.

At last, in Section 6, we show how to use a greedy approach to obtain an \(\Omega\mathopen{}\left( k^{-2/3} \right)\)-approximation algorithm for the problem called Precedence-Constrained Parallel Densest Subfamily (PCDST) with unit cost sets subject to precedence constraints which is an analog of the Parallel Densest Subfamily in the presence of precedence constraints.

As a consequence, we obtain an \(\frac{8e}{e-1}+\epsilon< 12.66\)-approximation for related machines, \(O\mathopen{}\left( \log m/\log\log m \right)\)-approximation for unrelated machines and \(O\mathopen{}\left( k^{2/3} \right)\)-approximation for unit time jobs, subject to precedence constraints. Note that even for \(m=1\), the presence of precedence constraints makes the problem inapproximable within a factor of \(O\mathopen{}\left( k^{1/12-\epsilon} \right)\) for any \(\epsilon>0\) unless the Planted Dense Subgraph conjecture fails [2]. These are the first results for the PMSSC to the best of our knowledge.

1.2 Related Work↩︎

The Set Cover is a cornerstone problem in the combinatorial optimization. Vazirani uses it as a prime example of use of various techniques in approximation algorithms in his book [4]. The greedy algorithm for this problem achieves an \(H_n\)-approximation guarantee, where \(H_n\) is the \(n\)-th harmonic number, and this is tight under the assumption that \(P\neq NP\) [5]. If each element belongs to at most \(f\) sets, then there exists a layering algorithm which achieves \(f\)-approximation. The related problem called Maximum Coverage is to cover maximum number elements with a given budget. The greedy algorithm for this problem achieves a \(\mathopen{}\left( 1-1/e \right)\)-approximation guarantee, and this is best possible as well (under \(P\neq NP\) ) [6]. Among important generalizations of this problem belongs the Submodular Optimization, which is to maximize a submodular function under certain constraints. Multiple variants of this problem have been studied starting with the seminal work of Nemhauser et al. [7].

The Min-Sum Set Cover problem was introduced by Feige et. al. [1] who showed that the greedy algorithm achieves \(4\)-approximation and it is NP-hard to improve this. Since then, their work has been extended in various directions. Azar et. al. [3] present a general framework for approximating min-sum ordering problems and they show that the greedy algorithm achieves \(4/\alpha\)-approximation guarantee, where \(\alpha\) is the approximation ratio for the problem of finding a densest subset. McClintock et. al. [2] consider a generalization of Min-Sum Set Cover where sets are precedence constrained, and they show that a modified greedy which uses the densest precedence-closed subfamily achieves a \(4/\alpha\)-approximation guarantee, given an \(\alpha=1/\sqrt{k}\)-approximation algorithm for the latter problem. Moreover, the problem cannot be approximated within the factor of \(O\mathopen{}\left( k^{1/12-\epsilon} \right)\) nor \(O\mathopen{}\left( n^{1/6-\epsilon} \right)\) for any \(\epsilon>0\) unless the Planted Dense Subgraph conjecture is false. These results have been further extended by Szyfelbein et. al. to an \(O^*\mathopen{}\left( \sqrt{k} \right)\)-approximation for both Precedence Constrained Set Cover [8] and Precedence Constrained Min-Sum Set Cover for the case when not all elements need to be covered, which requires non-greedy algorithms.

Parallel Task Scheduling is a well-studied problem in the scheduling literature. The problem \(P||C_{max}\) is strongly \(NP\)-hard and has an EPTAS running in \(2^{O\mathopen{}\left( 1/\epsilon\cdot \log\mathopen{}\left( 1/\epsilon \right)\cdot\log\log\mathopen{}\left( 1/\epsilon \right) \right)}\) time [9]. The \(Q||C_{max}\) also admits an EPTAS, but running in \({2^{O\mathopen{}\left( 1/\epsilon\cdot\log^4\mathopen{}\left( 1/\epsilon \right) \right)}}\) time [10]. However, \(R||C_{max}\) cannot be approximated within a factor of \(3/2-\epsilon\) for any \(\epsilon>0\), unless \(P=NP\) and the best known approximation algorithm for this problem achieves a factor of \(2\) [11]. The problem \(R||\sum C_j\) is polynomially solvable [12], however the addition of weights (\(R||\sum w_jC_j\)) makes it strongly \(NP\)-hard [13]. For \(Q||\sum w_jC_j\) a PTAS is known [14], but the \(R||\sum w_jC_j\) is APX-hard [15] and the curently best known approximation is \(1.488\) [16].

1.3 Motivation and Applicatons↩︎

The list of applications of Parallel Min-Sum Set Cover is beyond the scope of this work, hereby we showcase some of the more interesting examples:

1. Software testing: We have a system containing a set of features which we want to provide. We wish to verify whether they work properly, and if not, identify the faulty components. We have a set of tests at our disposal, each of which can verify some subset of features and a number of computers which can execute these tests. Moreover, we have a cost function associated with each test and each computer which denotes the amount of time required to execute that test on this computer. We want to schedule the tests on the computers in such a way that the average time required to verify the features is minimized.

2. Blackout fixing: We have a power grid (or any other type of large infrastructure) which is providing electricity to citizens. A massive failure occurs and we want to identify the source of the failure as soon as possible. We have a set of teams of workers at our disposal, each of which at any time can visit a chosen location and check whether some of its components is faulty. We wish to minimize the average time required to identify the source of the failure.

3. Iterative feature release: We have a software product which we want to provide to customers. We have a set of features which we want to implement, and a set of teams of workers at our disposal, each of which can be assigned to implement a certain component consisting of a subset of features at a given time. We want to schedule the work of the teams in such a way that the average time of feature implementation is minimized.

From the theoretical point of view, the Parallel Min-Sum Set Cover is a natural generalization of the classical Min-Sum Set Cover. Multiple combinatorial problems can be cast as scheduling problems which results in various, previously unexplored variants. In our work we show, that even in the multiple-machine setting we can obtain non-trivial approximation algorithms for PMSSC. Moreover, although our main procedure behaves in a greedy way, for non-identical machines the subroutine which finds the dense family of sets behaves in a non-greedy manner. Of particular interest is the case of related machines, where we use a technique which allows us to reduce the number of machines to \(O\mathopen{}\left( \log m \right)\), which may be of independent interest. In our setting this comes handy, since this reduces the FPT running time of the algorithm for Parallel Densest Subfamily to polynomial time.

2 Preliminaries↩︎

The input of the Parallel Min-Sum Set Cover (\(\mathrm{\small PMSSC}\)) is as follows: We are given a universe \(\mathcal{U}\) of \(n\) elements, a collection \(\mathcal{S}\) of \(k\) subsets of \(\mathcal{U}\), \(m\) machines and a cost function \(c\colon \mathcal{S}\times [m]\to \mathbb{N}\), where \([m]=\{1, 2, \dots, m\}\). The goal is to find a schedule \(\sigma\) of sets from \(\mathcal{S}\) on \(m\) machines such that the cost of the schedule is minimized. A schedule \(\sigma\) is a collection of \(m\) sequences of sets from \(\mathcal{S}\). Let \(S\in \mathcal{S}\) be some set scheduled in \(\sigma\) on machine \(j_S\in [m]\). Denote by \(\sigma[\dots S]\) the prefix of the schedule \(\sigma\) on machine \(j_S\) that ends with \(S\). The finish time of \(S\) is defined as \(\operatorname{ft}\mathopen{}\left( S \right)=\sum_{S'\in \sigma[\dots S]} c\mathopen{}\left( S', j_S \right)\). For an element \(u\in \mathcal{U}\), let \(S_u\ni u\) be the set \(S\) in \(\sigma\) minimizing \(\operatorname{ft}\mathopen{}\left( S \right)\). We define covering time of \(u\) as \(\operatorname{ct}\mathopen{}\left( u \right) = \operatorname{ft}\mathopen{}\left( S_u \right)\). The cost of a schedule \(\operatorname{cost}\mathopen{}\left( \sigma \right)=\sum_{u\in \mathcal{U}} \operatorname{ct}\mathopen{}\left( u \right)\) is the sum of covering times of all elements in \(\mathcal{U}\). We distinguish four cases of \(\mathrm{\small PMSSC}\) according to the cost function \(c\):

1. Unit cost sets: For every set \(S\in\mathcal{S}\), and \(j\in[m]\), \(c\mathopen{}\left( S, j \right)=1\).

2. Identical machines: For every set \(S\in\mathcal{S}\), and \(j\in[m]\), \(c\mathopen{}\left( S, j \right)=c\mathopen{}\left( S \right)\).

3. Related machines: For every set \(S\in\mathcal{S}\), and \(j\in[m]\), \(c\mathopen{}\left( S, j \right)=c\mathopen{}\left( S \right)/s\mathopen{}\left( j \right)\), where \(s\mathopen{}\left( j \right)\) is the speed of the machine and \(f\mathopen{}\left( j \right)=1/s\mathopen{}\left( j \right)\) is the effectiveness of the machine.

4. Unrelated machines: No additional conditions imposed on the cost function.

Let \(\mathcal{C}\subseteq \mathcal{S}\) and let \(\mathcal{U}'\subseteq \mathcal{U}\). The coverage of \(\mathcal{C}\) in \(\mathcal{U}'\) is defined as \(\operatorname{cov}\mathopen{}\left( \mathcal{C}, \mathcal{U}' \right)=\bigcup_{S\in \mathcal{C}} S\cap \mathcal{U}'\). If \(\mathcal{U}'=\mathcal{U}\), we simply write \(\operatorname{cov}\mathopen{}\left( \mathcal{C} \right)\). For a sequence of sets \(\pi=\mathopen{}\langle S_1, S_2, \dots, S_\ell \rangle\) the coverage is defined by \(\operatorname{cov}\mathopen{}\left( \pi, \mathcal{U}' \right)=\bigcup_{j=1}^{\ell} S_j \cap \mathcal{U}'\). Analogously, let \(\mathopen{}\left\{ \sigma\mathopen{}\left( j \right) \right\}_{j=1}^m\) be a collection of \(m\) sequences of sets. Then, the coverage of \(\sigma\) is defined as \(\operatorname{cov}\mathopen{}\left( \sigma, \mathcal{U}' \right)=\bigcup_{j=1}^{m} \operatorname{cov}\mathopen{}\left( \sigma\mathopen{}\left( j \right), \mathcal{U}' \right)\). We say that \(\sigma\) is a feasible solution if \(\operatorname{cov}\mathopen{}\left( \sigma \right)=\mathcal{U}\). Given an assignment of sets to machines \(\mathopen{}\left\{ \mathcal{F}\mathopen{}\left( j \right) \right\}_{j=1}^m\), denote by \(\mathopen{}\left| \mathcal{F} \right|=\max_{j\in [m]}\mathopen{}\left\{ \sum_{S\in \mathcal{F}\mathopen{}\left( j \right)} c\mathopen{}\left( S, j \right) \right\}\) the cost of the most expensive machine in \(\mathcal{F}\). The density of this assignment is defined as \(\Delta\mathopen{}\left( \mathcal{F}, \mathcal{U} \right) = \frac{\mathopen{}\left| \operatorname{cov}\mathopen{}\left( \mathcal{F}, \mathcal{U} \right) \right|}{\mathopen{}\left| \mathcal{F} \right|}\). In order to solve PMSSC efficiently we define the following key subproblem called Parallel Densest Subfamily: Given a universe \(\mathcal{U}\), a family of covering subsets \(\mathcal{S}\), \(m\) machines and a cost function \(c\times [m]\colon \mathcal{S}\to \mathbb{N}\), find an assignment of subsets to machines \(\mathopen{}\left\{ \mathcal{F}\mathopen{}\left( j \right) \right\}_{j=1}^m\) maximizing \(\Delta\mathopen{}\left( \mathcal{F}, \mathcal{U} \right)\). Note, that for any maximization problem, we adopt a convention that an \(\alpha\)-approximation algorithm is an algorithm that returns a solution with value at least \(\alpha\cdot \texttt{OPT}\), where \(\texttt{OPT}\) is the optimal value of the objective function. We will also need the Parallel Maximum Coverage (PMC) problem: Given a universe \(\mathcal{U}\), a family of covering subsets \(\mathcal{S}\), \(m\) machines, a cost function \(c\times [m]\colon \mathcal{S}\to \mathbb{N}\) and a budget \(B_j\) for every \(j\in[m]\), find an assignment of subsets to machines \(\mathopen{}\left\{ \mathcal{F}\mathopen{}\left( j \right) \right\}_{j=1}^m\) such that for every machine \(j\in [m]\) we have that \(\sum_{S\in\mathcal{F}\mathopen{}\left( j \right)} c\mathopen{}\left( S, j \right) \leq B_j\) and \(\mathopen{}\left| \operatorname{cov}\mathopen{}\left( \mathcal{F}, \mathcal{U} \right) \right|\) is maximized. An algorithm is a \(\mathopen{}\left( \alpha, \beta \right)\)-approximation algorithm for \(\mathrm{\small PMC}\) if it returns an assignment of subsets to machines \(\mathopen{}\left\{ \mathcal{F}\mathopen{}\left( j \right) \right\}_{j=1}^m\) such that for every machine \(j\in [m]\), \(\sum_{S\in\mathcal{F}\mathopen{}\left( j \right)} c\mathopen{}\left( S, j \right) \leq \beta\cdot B_j\) and \(\mathopen{}\left| \operatorname{cov}\mathopen{}\left( \mathcal{F}, \mathcal{U} \right) \right|\geq \alpha\cdot \texttt{OPT}\), where \(\texttt{OPT}\) is the optimal value of the objective function. Let \(C=\sum_{j=1}^{m}\sum_{S\in \mathcal{S}}c\mathopen{}\left( S, j \right)\) be a trivial upper bound on the length of any schedule.

We will also use the weighted Chernoff bound. The proof of this fact is a straightforward modification of the proof of the standard Chernoff bound and is provided in the Appendix.

3 General scheme of approximating \(\mathrm{\small PMSSC}\)↩︎

In this section we present a \(4/\alpha\)-approximation greedy algorithm for \(\mathrm{\small PMSSC}\) using an \(\alpha\)-approximation algorithm for Parallel Densest Subfamily. Assume we have an \(\alpha\)-approximation algorithm for Parallel Densest Subfamily. The algorithm is as follows:

Proof. Let \(\sigma\) be an optimal schedule. We will show that the schedule \(\pi\) returned by the above algorithm is a \(4/\alpha\)-approximation solution. We provide an adapted version of the histogram schrinkage argument used in various works on Min-Sum Set Cover [1]–[3].

Let \(\mathcal{F}_i\) be the assignment obtained in the \(i\)-th iteration of the while loop, \(R_i\) be the set of uncovered elements at the beginning of the \(i\)-th iteration and \(X_i\) be the set of elements covered for the first time in the \(i\)-th iteration. We have the following upper bound on the cost of the schedule \(\pi\): \(\sum_{i}\mathopen{}\left| R_i \right|\cdot\mathopen{}\left| \mathcal{F}_i \right|\), since in the worst case \(\mathcal{F}_i\) contributes the cost of \(\mathopen{}\left| \mathcal{F}_i \right|\) to covering time of all elements in \(R_i\).

Let \(\ell_i=\sum_{p=1}^{i}\mathopen{}\left| \mathcal{F}_i \right|\). Order the elements of \(\mathcal{U}\) by the time they are covered by \(\pi\). For each \(u\) we plot a rectangle of width \(1\) and height \(\ell_i\), where \(i\) is the index of the first \(\mathcal{F}_i\) which covered \(u\). Clearly, the area under this histogram is equal to \(\sum_{i}\mathopen{}\left| R_i \right|\cdot\mathopen{}\left| \mathcal{F}_i \right|\), which is an upper bound on the cost of \(\pi\). Moreover, by summing up over the values of the function, not over the elements (Lebesgue integral style), the area under the histogram can be partitioned into rectangles of width \(\mathopen{}\left| R_i \right|\) and height \(\mathopen{}\left| \mathcal{F}_i \right|\), which is equal to \(\sum_{i}\mathopen{}\left| R_i \right|\cdot\mathopen{}\left| \mathcal{F}_i \right|\). For a visual depiction see Figure 3.

Now, take any such strip and define \(h_i=\frac{\mathopen{}\left| \mathcal{F}_i \right|\cdot\mathopen{}\left| R_i \right|}{2/\alpha\cdot \mathopen{}\left| X_i \right|}\). We map this strip onto a column of height \(h_i\) and width \(\mathopen{}\left| X_i \right|/2\) positioned between \(\mathopen{}\left| R_i \right|\) and \(\mathopen{}\left| R_{i+1} \right|/2\) elements from the right-hand end of the histogram of some optimal solution \(\sigma\). It is easy to see that the area under this new plot is \(4/\alpha\) times smaller then the plot of \(\pi\). By \(\pi[\dots i]\) we denote the sets scheduled in \(\pi\) up to the end of the \(i\)-th iteration of the while loop. For any \(t\in \mathbb{N}\), define \(\sigma[\dots t]\) as the sets scheduled in \(\sigma\) up to the time \(t\).

Lemma 1. For every \(i\) such that \(R_i\) is not empty, we have that \(\mathopen{}\left| \operatorname{cov}\mathopen{}\left( \sigma[\dots \mathopen{}\left\lfloor h_i \right\rfloor], R_i \right) \right| \leq \mathopen{}\left| R_i \right|/2\).

Proof. Assume that there is at least one set in \(\sigma[\dots \mathopen{}\left\lfloor h_i \right\rfloor]\) not in \(\pi[\dots i-1]\). Otherwise, the claim is trivial since \(\mathopen{}\left| \operatorname{cov}\mathopen{}\left( \sigma[\dots \mathopen{}\left\lfloor h_i \right\rfloor], R_i \right) \right|=0\). In the \(i\)-th iteration of the while loop, we run an \(\alpha\)-approximation algorithm for Parallel Densest Subfamily with input \(R_i\) and \(\mathcal{F}\setminus\pi[\dots i-1]\). Since \(\sigma[\dots \mathopen{}\left\lfloor h_i \right\rfloor]\setminus \pi[\dots i-1]\) is a feasible solution for this instance, we get: \[\begin{align} \frac{\mathopen{}\left| \operatorname{cov}\mathopen{}\left( \sigma[\dots \mathopen{}\left\lfloor h_i \right\rfloor]\setminus \pi[\dots i-1], R_i \right) \right|}{\mathopen{}\left| \sigma[\dots \mathopen{}\left\lfloor h_i \right\rfloor]\setminus \pi[\dots i-1] \right|}\leq \frac{1}{\alpha} \cdot \frac{\mathopen{}\left| X_i \right|}{\mathopen{}\left| \mathcal{F}_i \right|} \end{align}\] Since none of the items in \(R_i\) are covered by \(\pi[\dots i-1]\) and \(\mathopen{}\left| \sigma[\dots \mathopen{}\left\lfloor h_i \right\rfloor]\setminus \pi[\dots i-1] \right|\leq h_i\), we have \(\mathopen{}\left| \operatorname{cov}\mathopen{}\left( \sigma[\dots \mathopen{}\left\lfloor h_i \right\rfloor], R_i \right) \right| = \mathopen{}\left| \operatorname{cov}\mathopen{}\left( \sigma[\dots \mathopen{}\left\lfloor h_i \right\rfloor]\setminus \pi[\dots i-1], R_i \right) \right|\leq \frac{1}{\alpha}\cdot \frac{\mathopen{}\left| X_i \right|}{\mathopen{}\left| \mathcal{F}_i \right|}\cdot h_i = \mathopen{}\left| R_i \right|/2\). ◻

The above lemma shows that after \(\mathopen{}\left\lfloor h_i \right\rfloor\) time in the optimal solution \(\sigma\), at most \(\mathopen{}\left| R_i \right|/2\) elements from \(R_i\) are covered. Therefore the plot of \(\sigma\) has to have a height of at least \(\mathopen{}\left\lfloor h_i \right\rfloor+1\geq h_i\) at the point \(\mathopen{}\left| R_i \right|/2\). The top-left corner of the column corresponding to \(h_i\) is at the point \(\mathopen{}\left( \mathopen{}\left| R_i \right|/2, h_i \right)\), which is below the plot of \(\sigma\). Therefore, since the plot of \(\sigma\) is non-decreasing, the entire column corresponding to \(h_i\) is below the plot of \(\sigma\). ◻

We use the following proposition:

The proof and the algorithms are provided in Section 4. By combining Theorem 2 with the above proposition, we obtain the main corollary of our work, which is the following:

4 Proof of Proposition 3: Parallel Densest Subfamily↩︎

4.1 Warm up: Identical machines and unit cost sets↩︎

For identical machines, given \(\epsilon>0\), \(\mathrm{\small PDS}\) has the following approximation algorithm:

In the case of unit set costs, the algorithm admits further simplification. Instead of assigning sets in a round robin manner we assign at most \(\mathopen{}\left\lfloor B/m \right\rfloor\) sets to each machine arbitrarily. The analysis is the same as above, however we can get rid of the factor of \(2\) in the approximation ratio, yielding a \(\frac{e-1}{e+\epsilon\cdot\mathopen{}\left( e-1 \right)}\)-approximation FPTAS.

4.2 Related machines↩︎

Now, we show how to extend this to related machines. For related and unrelated machines, we will use the \(\mathopen{}\left( \alpha, \beta \right)\)-approximation algorithm for Parallel Maximum Coverage. We use the following proposition:

The proof and the algorithm are provided in Section 5.

Fix \(\delta=\frac{\epsilon\cdot 2e}{e-1}\) and \(\kappa=\frac{\delta}{\delta+16}\) so that \(\frac{\mathopen{}\left( 1+\kappa \right)^4}{1-\kappa} \leq 1+\delta\). The algorithm for PDS is as follows:

4.3 Unrelated machines↩︎

To obtain an approximation algorithm for PDS on unrelated machines we use the polynomial time bicriteria \(\mathopen{}\left( (1-1/e)\cdot(1-\epsilon), O\mathopen{}\left( \log m/\log\log m \right) \right)\)-approximation algorithm for \(\mathrm{\small PMC}\):

5 Proof of Proposition 5: Parallel Max Coverage↩︎

In this section we prove Proposition 5 by presenting bicriteria \(\mathopen{}\left( (1-1/e)\cdot(1-\epsilon), O\mathopen{}\left( \log m/\log\log m \right) \right)\)-approximation algorithm for \(\mathrm{\small PMC}\) running in polynomial time, as well as one with approximation ratio of \(\mathopen{}\left( (1-1/e)\cdot(1-\epsilon), 1+\mu \right)\), running in time \(\text{poly}\mathopen{}\left( n, m, 1/\epsilon \right)+e^{O\mathopen{}\left( g(\mu)\cdot m \right)}\). We start by showing an ILP formulation of \(\mathrm{\small PMC}\). We modify the standard LP for the Maximum Coverage, by adding machine-indexed variables. We then show how to round the solution of the LP relaxation of this ILP.

We assume that all of the costs are normalized so that for every \(j\in [m]\), \(\sum_{i=1}^{k}c\mathopen{}\left( S, j \right)\leq 1\). This can be achieved by dividing all costs and the budget by an appropriate constant. This transformation does not impact the optimality of a solution nor the approximation ratios. Due to this normalization, we can assume that for every \(j\in [m]\), \(B_j\leq 1\) without loss of generality.

5.1 ILP formulation of \(\mathrm{\small PMC}\)↩︎

Let \(x_{S,j}\in\mathopen{}\left\{ 0,1 \right\}\) be a binary variable denoting whether set \(S\) is assigned to machine \(j\) and \(y_u\in\mathopen{}\left\{ 0,1 \right\}\) be a binary variable denoting whether \(u\in \mathcal{U}\) is covered by the selected sets. The ILP is as follows: \[\begin{align} & \max \sum_{u \in \mathcal{U}} y_u \\ \text{s. t.} \quad & \sum_{S \ni u} \sum_{j=1}^m x_{S,j} \geq y_u \quad \forall u \in \mathcal{U}\\ & \sum_{S\in\mathcal{S}} c_{S,j} \cdot x_{S,j} \leq B_j \quad \forall j \in [m] \\ & x_{S,j} \in \{0,1\} \quad \forall S \in \mathcal{S},j \in [m] \\ & y_u \in \{0,1\} \quad \forall u \in \mathcal{U} \end{align}\]

5.2 Rounding the LP relaxation↩︎

To obtain our first approximation algorithm for \(\mathrm{\small PMC}\), we set \(R=\mathopen{}\left\lceil \frac{2-2/e}{\epsilon^2}\cdot\ln n \right\rceil\), \(\delta=\frac{4\ln m}{\ln\ln m}\) and for the second algorithm we set \(R=\max\mathopen{}\left\{ \mathopen{}\left\lceil \frac{2-2/e}{\epsilon^2}\cdot\ln n \right\rceil, \frac{\ln\mathopen{}\left( m \right)}{-\ln\mathopen{}\left( 1-\mathopen{}\left( 1-f(\mu) \right)^m \right)} \right\}\), where \(f\mathopen{}\left( x \right)=\frac{e^x}{\mathopen{}\left( 1+x \right)^{1+x}}\) and \(\delta=\mu\). The procedure is as follows:

We first solve the LP relaxation of the ILP formulation, which allows the variables \(x_{S,j}\) and \(y_u\) to take values in the range \([0,1]\). We repeat the following process for \(\mathopen{}\left\lfloor \frac{2-2/e}{\epsilon^2}\cdot\ln n \right\rfloor\) times and pick the best solution: For every machine \(j\in [m]\) and every set \(S\in \mathcal{S}\) we select set \(S\) for machine \(j\) with probability \(x_{S,j}\), or we do not select it with probability \(1-x_{S,j}\). This way we obtain a feasible solution \(\mathcal{C}\) for \(\mathrm{\small PMC}\). Let \(X_{S,j}\) be the random variable that is equal to \(1\) if set \(S\) is selected for machine \(j\), and \(0\) otherwise. Let \(Y_u\) be the random variable that is equal to \(1\) if element \(u\) is covered by the selected sets, and \(0\) otherwise. Let \(C_j=\sum_{S\in\mathcal{S}} c_{S,j} \cdot X_{S,j}\) be the cost of sets assigned to machine \(j\) in the LP solution. We have the following lemma regarding the probability of exceeding the budgets \(B_j\).

By repeating the rounding \(\mathopen{}\left\lceil \frac{2-2/e}{\epsilon^2}\cdot\ln n \right\rceil\) times, we have that the probability that the returned solution covers less then \(\mathopen{}\left( 1-\epsilon \right)\cdot\mathopen{}\left( 1-1/e \right)\cdot\texttt{OPT}\) elements is at most: \[\begin{align} \exp\left\{ -\frac{\epsilon^2}{2}\cdot\mathopen{}\left( 1-\frac{1}{e} \right)\cdot\mathopen{}\left\lceil \frac{2-2/e}{\epsilon^2}\cdot\ln n \right\rceil \right\} \leq \exp\left\{ -\ln n \right\}= \frac{1}{n}. \end{align}\]

6 Precedence constraints↩︎

Throughout this section we consider the case of unit cost sets and we assume that the precedence constraints between the sets are given by a directed acyclic graph \(G\) on \(\mathcal{S}\). Let \(d\) be the length of the longest path in \(G\). By \(\mathcal{P}\mathopen{}\left( S \right)\) denote the closure of \(S\in\mathcal{S}\) in \(G\), i. e. the set of all of its predecessors (including \(S\)). We will assume that any assignment of sets to the machines we consider has some ordering. We say that an assignment of sets to machines \(\mathopen{}\left\{ \mathcal{F}\mathopen{}\left( j \right) \right\}_{j=1}^m\) is precedence-closed if for every \(S\in \mathcal{F}\mathopen{}\left( j \right)\), all predecessors of \(S\) (excluding itself) are scheduled before \(S\). The density of a precedence-closed assignment \(\mathopen{}\left\{ \mathcal{F}\mathopen{}\left( j \right) \right\}_{j=1}^m\) is defined as \(\Delta\mathopen{}\left( \mathcal{F}, \mathcal{U} \right) = \frac{\mathopen{}\left| \operatorname{cov}\mathopen{}\left( \mathcal{F}, \mathcal{U} \right) \right|}{\mathopen{}\left| \mathcal{F} \right|}\). The Precedence-Constrained Parallel Densest Subfamily (PCDST) problem is to find a precedence-closed assignment of sets to machines maximizing this density. To solve this problem, we significantly alter the algorithm of [2].

By applying the greedy algorithm for \(\mathrm{\small PMSSC}\) with the above algorithm for finding a precedence-closed assignment with good density, using analysis similar to the one in Section 3 we get the following result:

Recall, that evidence exists that no algorithm with approximation ratio of \(O\mathopen{}\left( k^{1/12-\epsilon} \right)\) nor \(O\mathopen{}\left( n^{1/6-\epsilon} \right)\) exists even for the case when \(m=1\), if one assumes the \(\mathrm{\small PDS}\). Closing the gap between this and \(O\mathopen{}\left( k^{2/3} \right)\) remains an open problem.

7 Conclusions and open problems↩︎

We give \(12.66\)-approximation algorithm for the Parallel Min-Sum Set Cover problem on related machines, \(O\mathopen{}\left( \log m/\log\log m \right)\)-approximation for unrelated machines and \(O\mathopen{}\left( k^{2/3} \right)\)-approximation for precedence constrainted unit cost sets. All of these results are based on obtaining good approximation algorithms for the Parallel Densest Subfamily problem, which is then used in a greedy manner.

It would be of interest to incorporate different scheduling constraints, such as release dates on the sets, or due dates on the elements. We note that for the release dates, all of our algorithms for variants without precedence constraints can be easily adapted with a loss of multiplicative factor of \(2\) in the approximation ratio. This can be done during the guessing step of our algorithm. Upon deciding on a budget \(B\), we can set the cost of all sets with release date larger than \(B\) to infinity, which forces the algorithm to not select them. The rest of sets can be scheduled by simply waiting for \(B\) units of time before starting to schedule any set.

8 Weighted Chernoff Bound Derivation↩︎

References↩︎