A 4.509 4.509 -Approximation Algorithm for Generalized Min Sum Set Cover

Amey Bhangale, Yezhou Zhang · 2026

Read A 4.509 4.509 -Approximation Algorithm for Generalized Min Sum Set Cover by Amey Bhangale, Yezhou Zhang (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-2605-10031.txt.

Introduction

Bhangale and Zhang tackle the generalised min-sum set cover problem. Given hyperedges, groups of vertices each needing a set number of its vertices to appear, the task is to order the vertices to minimise total cover time. A hyperedge counts as covered once enough of its vertices have shown up. The previous best guarantee was 4.642, and the authors improve it to 4.509.

Their approach keeps the linear-programming framework of Bansal, Batra, Farhadi and Tetali. It sharpens the analysis, narrowing the gap toward the lower bound of 4 that holds if P differs from NP. The proof exploits the program's constraints in a non-trivial way. It develops new lower-tail bounds for sums of independent Bernoulli variables, results the authors note may interest readers beyond this problem.

Catalog record

CREATORAmey Bhangale, Yezhou Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.10031

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A 4.509 4.509 -Approximation Algorithm for Generalized Min Sum Set Cover Amey Bhangale, Yezhou Zhang Abstract We study the generalized min-sum set cover (GMSSC) problem, where given a collection of hyperedges E E with arbitrary covering requirements { k e ∈ ℤ + : e ∈ E } \{k_{e}\in\mathbb{Z}^{+}:e\in E\} , the objective is to find an ordering of the vertices that minimizes the total cover time of the hyperedges. A hyperedge e e is considered covered at the first time when k e k_{e} of its vertices appear in the ordering. We present a 4.509 4.509 -approximation algorithm for GMSSC, improving upon the previous best-known guarantee of 4.642 4.642 [ 2 , SODA’21] . Our approach retains the general LP-based framework of Bansal, Batra, Farhadi, and Tetali [ 2 ] but provides an improved analysis that narrows the gap toward the lower bound of 4 4 -approximation assuming P ≠ \neq NP. Our analysis takes advantage of the constraints of the linear program in a nontrivial way, along with new lower-tail bounds for the sums of independent Bernoulli random variables, which could be of independent interest. 1 Introduction In this paper, we study approximation algorithms for the following related problems. Min Sum Set Cover Problem: The min sum set cover problem (MSSC) takes a universe of n elements, denoted as [n] , as input and a collection of it subsets. Given a permutation of all elements in [n] , a subset S is considered covered at the earliest time an element from S appears in the permutation. The goal of the min sum set cover problem is to find a permutation of [n] that minimizes the sum of the cover time of all given subsets. Alternatively, this problem can be described on a hypergraph: given a hypergraph G=(V,H) with n vertices and a set of hyperedges e\in H . For a schedule (permutation) of n vertices, the cover time is defined as the earliest time that one of v\in e appears in the schedule. The goal is to find a schedule that minimizes the sum of the cover time of all hyperedges. This problem was formally defined in [ 6 ] , which also introduced a 4 -approximation greedy algorithm and a matching hardness result. Generalized Min Sum Set Cover Problem: The generalized min sum set cover problem (GMSSC), also known as the multiple intents re-ranking problem generalized MSSC by assigning each hyperedge an individual cover requirement k_{e}\leq|e| , such that the hyperedge is considered at the earliest time when k_{e} of its vertices appear in the schedule. The problem was first introduced by Azar, Gamzu, and Yin in [ 1 ] , which also provided an O(\log(\max{k_{e}})) -approximation algorithm for the problem. Bansal, Gupta, and Krishnaswamy first provided a constant, 485 -approximation in [ 3 ] with a linear program relaxation, which included strengthening constraints known as KC (Knapsack Cover) inequalities from [ 5 ] . Skutella and Williamson later improved the approximation factor to 28 in [ 11 ] by applying the \alpha -point rounding algorithm to the LP relaxation, and Im, Sviridenko, and Zwaan further improved the factor to 12.4 in [ 9 ] . Recently, Bansal, Batra, Farhadi, and Tetali gave a 4.642 -approximation in [ 2 ] by adding a linear transformation, or the kernel, to the LP fractional optimal solution and rounding based on the adjusted solution. This remains the best-known approximation to date. The hardness of GMSSC is 4-\epsilon , derived from MSSC in [ 6 ] . Min Latency Set Cover Problem: The min latency set cover problem, first formally studied in [ 7 ] , is a special case of GMSSC where each hyperedge has a cover requirement k_{e}=|e| . It is a well-studied problem, also known as the special case of the classic precedence-constrained scheduling problem, and has many 2 -approximation algorithms (see, e.g, [ 10 ] for a survey). Bansal and Khot proved the Unique-Game hardness of this problem is 2-\epsilon in [ 4 ] . 1.1 Our Results Our main theorem improves the 4.624 -approximation for GMSSC given by Bansal, Batra, Farhadi, and Tetali in [ 2 ] . Theorem 1.1 . There exists a 4.509 -approximation algorithm for the generalized min sum set cover (GMSSC) problem. In [ 2 ] , the authors gave an approximation algorithm for GMSSC and showed that the algorithm achieves an approximation ratio of 4.624 . They also remarked that the numerical analysis suggests that the approximation factor is no more than 4.5232 , even though they were unable to prove this analytically. Finally, they showed that getting better than a 4.509 factor approximation has a natural bottleneck for their approach. Towards proving the main theorem above, we provide a tighter analysis of their algorithm and show that it indeed achieves a 4.509 approximation ratio. Our analysis leverages the linear program’s constraints in a non-trivial manner along with new lower-tail bounds for the sums of independent Bernoulli random variables, which could be of independent interest (see Section 1.2 for more details). Our second theorem gives a 2 -approximation algorithm for the min latency set cover problem using the framework of Bansal, Batra, Farhadi, and Tetali [ 2 ] , improving upon the e=2.718\ldots approximation algorithm given in the same paper. Theorem 1.2 . There exists a 2 -approximation algorithm for the min latency set cover problem. Recall that a 2 -approximation algorithms were already known before [ 10 ] . We designed a new kernel which, when plugged into the framework of [ 2 ] , gives the optimal approximation algorithm for the min latency set cover problem. In [ 2 ] , the authors already showed that their framework gave an optimal 4 -approximation algorithm for MSSC (all k_{e}=1 ). Theorem 1.2 now shows that the framework provides an optimal approximation algorithm (assuming the Unique Games Conjecture) for min sum latency set cover (all k_{e}=|e| ). It would be interesting to see if it gives an optimal approximation algorithm for GMSSC (arbitrary k_{e} ). 1.2 Techniques This section provides an overview of the LP-rounding based algorithmic techniques employed in this paper. The foundation of our approach lies in the work of [ 3 ] , which defined a commonly used linear program (LP) for MSSC and GMSSC. This LP returns a fractional solution x where x_{v,t} is an indicator of whether vertex v is scheduled at time t . The core LP constraint is given by \sum_{v\in e}\sum_{t^{\prime}<t}x_{v,<t}\geq\sum_{t^{\prime}<t}x_{e,t^{\prime}},\quad\forall e,t, where \sum_{t^{\prime}<t}x_{e,t^{\prime}} indicates the fraction of edge e covered at time t . However, a simple randomized rounding algorithm, rounding based on \sum_{t^{\prime}\leq t}x_{v,t^{\prime}} , proves ineffective even for MSSC. This is because if the LP fractionally covers a hyperedge of n vertices by scheduling each vertex to the extent of 1/n at time t , this approach leaves this hyperedge uncovered with probability (1-1/n)^{n}\approx 1/e\gg 0 for any time after t . For a long period after t , the LP solver may consider this hyperedge covered, but yet no vertex might be scheduled in an integral solution, leading to an arbitrarily large approximation ratio. To overcome this, a linear transform, or kernel K , was introduced and applied to

Read the complete text