Min-Sum Set Cover on Parallel Machines
Michał Szyfelbein · 2026
Read Min-Sum Set Cover on Parallel Machines by Michał Szyfelbein (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-11388.txt.
Introduction
Szyfelbein generalizes min-sum set cover to parallel machines, with m set-sequences. An alpha-approximation for parallel densest subfamily yields a four-alpha approximation for the cover problem. That gives four-e-over-e-minus-one plus epsilon for identical machines and four times its square for unrelated machines. A new knapsack coverage approximation underpins the latter result. Unit-cost sets with precedence constraints admit order k-to-the-two-thirds; out-forest constraints improve this to order log k, tight unless NP sits inside quasi-polynomial randomized time.
Catalog record
| CREATOR | Michał Szyfelbein |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62748 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.11388
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Min-Sum Set Cover on Parallel Machines Michał Szyfelbein Abstract Consider the classical Min-Sum Set Cover problem: We are given a universe 𝒰 \mathcal{U} of n n elements and a collection 𝒮 \mathcal{S} of k 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 u is the cost of all sets that appear in the sequence before u 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 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 − ϵ , O ( log m / log log m ) ) (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 ) 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 ) O(\log m) unrelated machines, to get an 8 e e + 1 + ϵ < 12.66 \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 ) O(k^{2/3}) approximation ratio. 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. S_{1}(1) S_{2}(2) S_{3}(3) S_{4}(2) S_{5}(4) S_{6}(5) S_{7}(1) S_{8}(3) S_{9}(2) S_{10}(4) u_{1} u_{2} u_{3} u_{4} u_{5} u_{6} u_{7} u_{8} u_{9} u_{10} u_{11} u_{12} u_{13} u_{14} u_{15} u_{16} u_{17} u_{18} u_{19} u_{20} Example identical machine PMSSC instance: sets with costs at the top, universe at the bottom. time 0 1 2 3 4 5 6 7 8 9 10 M_{1} M_{2} M_{3} S_{1} S_{2} S_{5} S_{4} S_{6} S_{7} S_{3} S_{8} Example schedule on 3 machines of cost 83 , note that S_{9} and S_{10} are not scheduled. Figure 1: An example instance and a feasible schedule for Parallel Min-Sum Set Cover . 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. [ 5 , 13 , 6 ] . 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.