A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover

Our main theorem improves the $4.624$-approximation for GMSSC given by Bansal, Batra, Farhadi, and Tetali in [2].

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\mathrm{\dots }$ approximation algorithm given in the same paper.

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 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$).

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

where indicates the fraction of edge $e$ covered at time $t$. However, a simple randomized rounding algorithm, rounding based on ${\sum }_{t^{\prime }\le 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 the fractional optimal solution $x$ from the LP in [2]. The standard $\alpha$-point randomized rounding was then applied to $Z=Kx$ to obtain a feasible integral solution. Using a kernel $K(t,t^{\prime })=\beta /t(t^{\prime }\le t)$, for $\beta =2$, in [2], the authors achieved a $4$-approximation for MSSC, which corresponded to the known hardness result. This was accomplished by analyzing the expected cover time of a hyperedge in the fractional optimal solution $x$, denoted $c_x(e)$, and its corresponding expected time in the integral solution $z$, denoted $c_z(e)$, along with a random tie-breaking rule for the final integral solution. While $c_x(e)$ was obtained from the optimal fractional solution, $c_z(e)$ was related to the sum of random Bernoulli variables. The approximation factor was then formulated as a convex optimization problem involving the ratio $c_z(e)/c_x(e)$. Through convex optimization techniques, it was proven that the worst-case scenario occurs when the LP solver assigns the extent $1/n$ to all vertices. Nevertheless, the $\beta /t$ kernel effectively increases the probability of scheduling $v\in e$ over time, leading to a feasible solution.

For the GMSSC problem, the best known hardness is $4$, and all previous approximations follow the extended analysis of MSSC. In [3], an unbounded integrality gap is demonstrated for the natural extended LP for GMSSC, and a set of strengthening constraints, KC (Knapsack Cover) inequalities from [5], was introduced for GMSSC.

The KC inequalities eliminated the unbounded integrality gap and enabled the proof of several constant-factor approximation algorithms. However, applying the same algorithm and analysis to GMSSC in [2] yielded only a $4.642$-approximation factor. This result left a gap between GMSSC and MSSC, and the method to eliminate this gap remained unknown. For instance, if $k_e-1$ vertices are already scheduled in the integral solution (let $S$ be the set of these vertices), the above KC inequality effectively transforms into a constraint in the LP for MSSC. This suggests that GMSSC could potentially be reduced to MSSC after a certain time.

Our paper aims primarily to eliminate this gap between GMSSC and MSSC after a certain time in the scheduling. To this end, we address a key analytical challenge in GMSSC: for a hyperedge $e$, the remaining cover requirement at time $t$, $k_e(t)$, potentially decreases over time as vertices are getting scheduled. This dynamic nature makes the probability of covering $e$ difficult to accurately express with a single function. We establish a novel upper bound $P^{k_e(t)}$ on the probability that a hyperedge $e$ remains uncovered at time $t$, explicitly involving $k_e(t)$. Furthermore, by leveraging multiple KC inequalities, we demonstrate that the core KC inequality (after applying the kernel) can be more accurately expressed as:

where $A_e(t)$ is the set of vertices guaranteed to be scheduled in the integral solution before time $t$, $\delta (t)$ is a crucial gap extracted from other KC inequalities.

Consequently, we derive a more precise expression for $c_z(e)$, the expected cover time in the integral solution. More precisely, since a vertex $v\in e\setminus A_e(t)$ is scheduled at time $t$ with probability in the rounding algorithm, the probability that $e$ is not covered at time $t$ is precisely the probability that at most $k_e(t)-1$ vertices from $e\setminus A_e(t)$ are scheduled before time $t$. If we let $P^k(x)$ to denote an upper bound on $\mathrm{Pr}[S\le k-1]$ if $kx=𝔼[S]$ where $S$ is the sum of Bernoulli random variables, then

where $t_e$ is a special time extracted from the LP solution. Compared to previous results, where (here, the quantity is an upper bound on the probability if $e$ is not covered at time $t$, independent of $k_e(t)$, proved in [2]), our expression more precisely reflects the probability of covering the hyperedge assuming that $k_e(t)$ is known. This allows for a more fine-grained analysis in terms of the change of $k_e(t)$ over time. Accordingly, we present several extended convex optimization results to argue that the worst-case behavior of GMSSC is similar to that of MSSC. Crucially, the existence of $\delta (t)$ and the properties of $P^{k_e(t)}$ allow us to prove that the worst-case scenario always involves $k_e(t)$ reducing to $1$ prior to $t_e$. On a more technical side, we give a refined upper bound on $P^k(x)$ in Theorem 4, and use these bounds to relate various terms in the expression (1) for $c_z(e)$ as $t$ increases. This more refined analysis yielded a $4.509$-approximation for GMSSC.

Beyond GMSSC, we also study the min latency set cover problem. While $2$-approximation algorithms are already known for this problem, we explore whether this LP framework can yield a matching approximation. In the min latency set cover problem, the LP solver needs to schedule all vertices of a hyperedge before it is considered covered. However, a simple randomized algorithm again proves insufficient. If the LP assigns an extent of $1-1/n$ to all vertices of a hyperedge, making the edge almost scheduled fractionally, the simple randomized algorithm covers this hyperedge at time $t$ with probability ${(1-1/n)}^n\approx 1/e$, which is much less than $1$. Consequently, we adopt a kernel:

which retains the property of increasing the probability of scheduling a vertex over time, but at a faster rate, as a divergent kernel is not required here. This approach, using a similar analysis, yields a 2-approximation. Although this result for the min latency set cover is not novel, it highlights the robustness and power of this LP-rounding framework and offers insights that could potentially lead to further improvements in the approximation factor for GMSSC.

Section 2 presents our primary analysis regarding the Generalized Minimum Sum Set Cover (GMSSC) problem. Specifically, we begin by briefly introducing the linear program, its relaxation, and the rounding algorithm from [2] in Sections 2.1 and 2.2, respectively. Our main contribution, detailed in Section 2.3, is the achievement of a $4.509$-approximation factor within this LP-rounding based framework.

Section 3 focuses on the min latency set cover problem, where we prove that this algorithm achieves a $2$-approximation using a distinct kernel compared to the MSSC/GMSSC approach. Finally, Section 4 establishes a new tail bound on the sum of Bernoulli random variables, which is crucial for the analysis presented in Section 2.3.

Assume that time is discrete and that time $t\in \{1,2,\mathrm{\dots }\}$, refers to the time interval $(t-1,t]$. $e$ refers to an edge and a hyperedge interchangeably. For each vertex $v$ and time $t$, there is a variable $x_{v,t}$, a 0-1 indicator of whether $v$ is assigned at time $t$. For each edge $e$ and time $t$, there is a variable $u_{e,t}$ intended to be $1$ if $e$ is uncovered at the beginning of $t$. The following LP program and relaxation for MSSC was introduced in [3]:

The constraint (2) ensures that at most one vertex is scheduled simultaneously. The constraint (3) guarantees that $u_{e,t}$ can be set to 0 only if some $v\in e$ is scheduled strictly before $t$.

For GMSSC, the demands $k_e$ are arbitrary, so the natural extension of (3),

becomes extremely weak. For example, if a hyperedge has $100$ vertices to cover, and the LP solver assigns to $99$ vertices but sets all other vertices to $0$. In such a case, the natural extension of (3) allows the LP solver to set $u_{e,t}=0.01$, and $e$ is almost covered in the fractional solution. However, since there are only $99$ vertices with , we are unable to obtain a valid integral solution in any case. Consequently, the Knapsack Cover (KC) Inequalities were introduced to replace (3) and strengthen the linear program in [3].

The KC inequalities guarantee that the LP solver can only consider this hyperedge $e$ covered when $k_e$ many vertices are almost scheduled.

Once the LP solver provides the optimal fractional solution $x$, we shall apply a rounding algorithm to $x$ to generate the integral solution. However, directly rounding may not guarantee a feasible integral solution. For example, when $k_e=1$, the LP solver can set ${\sum }_{t^{\prime }\le t}{x}_{v,t^{\prime }}=1/n\to 0$ for all $v\in e$. The challenge is that we may not schedule any vertex for a long period in the rounding procedure, since the probability is negligible. Therefore, we apply an additional transformation to $x$ to ensure that the integral solution gives a feasible schedule after the LP solver covers the edge. For all $v$ and $t$, we apply the following transformation,

The new solution $z=Kx$ will no longer satisfy the constraints in the original linear program, but $z$ can be rounded to a feasible schedule if $K$ is chosen properly. The rounding algorithm is as follows:

After the rounding procedure, the approximation algorithm gives the desired integral solution $\sigma$.

For a vector $x_v$, define

For the GMSSC problem, we select the kernel,

Note that $\beta =2.043$ in our final setting. Correspondingly,

This kernel ensures that even if , eventually reach $1$ for some large $T$.

Fix an edge $e$ and denote the cover time of $e$ in the LP as $c_x(e)$

Let $x_{e,t}=u_{e,t}-u_{e,t+1}$, then $c_x(e)$ can be written as

Additionally, define ${\text{Cov}}_{\sigma }(e)$ as the cover time of $e$ in $\sigma$. Similarly, ${\text{Cov}}_{\tau }(e)$ is the cover time of $e$ in $\tau$.

According to the rounding procedure, each vertex $v\in e$ will be scheduled with probability at time $t$. Let , then for each vertex $v$, the event whether $v$ will be scheduled can be considered as a Bernoulli random variable with success probability $Y_{v,t}\sim B(y_{v,t})$. Furthermore, the event that edge $e$ is scheduled at time $t$ is determined by the sum of $|e|$ independent Bernoulli random variables. Let $p_t(e)$ be the probability that $e$ is not scheduled at time $t$ in $\tau$. By the definition of ${\text{Cov}}_{\tau }(e)$ and the above analysis,

Let $S={\sum }_{v\in e}{Y}_{v,t}$, then $𝔼[S]={\sum }_{v\in e}{y}_{v,t}$. However, it is a challenge to analyze all vertices in $e$ simultaneously. The Hoeffding inequality, in [8], gives an upper bound on (9).

This lemma allows us to describe the sum of Bernoulli random variables using $𝔼[S]$. Remark that the bounds in Lemma 3 can be further bounded by some exponential bound derived from Poisson distributions.

Up to this point, the above analysis is virtually identical to the framework in [2]. However, there are some gaps in the framework that need to be addressed. Let $z_e=K{x}_e$, and consider the following KC inequalities

Apply the kernel $K$ to both sides, we have

Since corresponds to $y_{v,t}$ and corresponds to $x_{e,t}$, the KC inequalities potentially allow us to bound $𝔼[S]$ with $z_{e,t}$ or $x_{e,t}$. However, if for some vertices, this approach fails as . Thus, fix a time $t$, define , $B_e(t)=e\setminus A_e(t)$, and let $k_e(t)=|B_e(t)|$. Note that the vertices in $A_e(t)$ are definitely scheduled before time $t$ in the schedule $\tau$. We have

Or equivalently,

The challenge arises from the fact that $k_e(t)$ will decrease over time, so even the bound in Lemma 3 changes. In [2], the authors gave a common upper bound on $\mathrm{Pr}[S\le k-1]$ for all $k$ as a function of $\frac{𝔼[S]}{k}$. Since it is independent of $k$, it is always “safe” as $k_e(t)$ changes. However, such a safe bound is not tight for any $k_e(t)$ and introduces some loss. To improve, we need to process the KC inequalities with caution and extract more information from them.

First, for any fixed $k_e(t)$, we show the exponential upper bound for $p_t(e)$. We prove the following lemma that further upper bounds Lemma 3.