# Greedy heuristics and linear relaxations for the random hitting set problem

Gabriel Arpino1 1University of Cambridge, CB2 1PZ Cambridge, UK
<EMAIL_ADDRESS>,  Daniil Dmitriev2 2ETH Zürich and ETH AI Center, 8092
Zürich, Switzerland<EMAIL_ADDRESS>and  Nicolo Grometto3
3Princeton University, Sherrerd Hall, Princeton, NJ 08540, USA
<EMAIL_ADDRESS>
###### Abstract.

Consider the _Hitting Set_ problem where, for a given universe
$\mathcal{X}=\left\\{1\ldots,n\right\\}$ and a collection of subsets
$\mathcal{S}_{1},\ldots,\mathcal{S}_{m}$, one seeks to identify the smallest
subset of $\mathcal{X}$ which has nonempty intersection with every element in
the collection. We study a probabilistic formulation of this problem, where
the underlying subsets are formed by including each element of the universe
with probability $p$, independently of one another. For large enough values of
$n$, we rigorously analyse the average case performance of Lovász’s celebrated
greedy algorithm [10] with respect to the chosen input distribution. In
addition, we study integrality gaps between linear programming and integer
programming solutions of the problem.

###### Key words and phrases:

Hitting Set, Random Hypergraph, Integrality Gap, Greedy Algorithm

##  1\. Introduction

Hitting Set is a classical problem in combinatorial optimization which, for a
given ground set $\mathcal{X}:=\left\\{1,...,n\right\\}$ of elements and a
collection $\mathcal{C}:=\left\\{\mathcal{S}_{1},...,\mathcal{S}_{m}\right\\}$
of subsets of $\mathcal{X}$, asks to identify the smallest set
$\mathcal{S}\subseteq\mathcal{X}$ that intersects every subset in
$\mathcal{C}$. Hitting Set arises naturally from the study of _Minimum Vertex
Covers on Hypergraphs_ (MVCH), upon viewing hyperedges as subsets and vertices
as elements of the ground set. In addition, it is dual to the _Set Cover_
problem [12], which has a rich history in computational complexity theory,
including appearing as one of Karp’s 21 NP-complete problems. The aim of the
present work is to expand our understanding of the hardness of typical Hitting
Set instances, by analysing its average-case complexity with respect to a
large class of random inputs generated by assigning each element of the ground
set to any subset with fixed probability $p$, independently. To further
delineate the purpose of this work, let us recall that Hitting Set has the
following integer programming (IP) formulation,

(1.1) $\text{val}\textsubscript{{IP}}:=\begin{cases}\begin{aligned}
&\underset{{\boldsymbol{x}}}{\text{minimize}}&&\|{\boldsymbol{x}}\|_{1}\\\
&\text{subject
to}&&{\boldsymbol{A}}{\boldsymbol{x}}\geq\mathbf{1},\>{\boldsymbol{x}}\in\left\\{0,1\right\\}^{n},\end{aligned}\end{cases}$

where the $i$-th row of ${\boldsymbol{A}}\in\left\\{0,1\right\\}^{m\times n}$
provides a binary encoding of the membership of the elements of $\mathcal{X}$
in the set $\mathcal{S}_{i}$ and $\mathbf{1}:=(1,\ldots,1)\in\mathbb{R}^{m}$.
With the vertex cover formulation of the problem at hand, we note that
${\boldsymbol{A}}$ consists of the incidence matrix of the underlying
hypergraph. In particular, the first constraint in (1.1) ensures that each set
in $\mathcal{C}$ is hit by a prescribed candidate solution vector. A natural
convex relaxation is obtained by allowing fractional solutions, and may be
expressed as the following linear program (LP),

(1.2) $\text{val}\textsubscript{{LP}}:=\begin{cases}\begin{aligned}
&\underset{{\boldsymbol{x}}}{\text{minimize}}&&\|{\boldsymbol{x}}\|_{1}\\\
&\text{subject
to}&&{\boldsymbol{A}}{\boldsymbol{x}}\geq\mathbf{1},\>{\boldsymbol{x}}\in[0,1]^{n}.\end{aligned}\end{cases}$

Whilst clearly
$\text{val}\textsubscript{{LP}}\leq\text{val}\textsubscript{{IP}}$, tightness
need not hold in general. In fact, for $m=n$ and
${\boldsymbol{A}}\in\left\\{0,1\right\\}^{n\times n}$ chosen such that each
row and column contains exactly $k$ ones, for some fixed $1<k<n$, an optimal
solution is provided by
${\boldsymbol{x}}^{*}_{\texttt{LP}}=\left(1/k,...,1/k\right)$, which is not
integral, thus leading to a strictly smaller objective whenever $n/k$ is not
an integer. This evidences the existence of a significant _integrality gap_ ,
quantified by the ratio
$\text{val}\textsubscript{{IP}}/\text{val}\textsubscript{{LP}}$. In [10],
Lovász proved an essentially optimal worst-case upper bound on the Hitting Set
multiplicative integrality gap of $1+\log d_{\mathtt{max}}$, where
$d_{\mathtt{max}}$ corresponds to the maximum degree in the underlying
hypergraph. This is obtained by analysing the Greedy algorithm (Algorithm 1),
which constructs a vertex cover by sequentially adding vertices with the
highest degree amongst the uncovered edges, and will be discussed in more
detail in the next sections. However, in many natural examples, the maximum
degree $d_{\mathtt{max}}$ grows with the number of vertices in the hypergraph,
thus leading to progressively worse bounds for increasingly large hypergraphs.
Besides being arguably the most natural candidate for solving Hitting Set, the
greedy algorithm has been shown to be essentially the best possible polynomial
time approximation algorithm [13] for the worst-case instances of this
classical problem. In particular, the greedy algorithm has an approximation
ratio of $O(\log m)$, thus finding coverings that may be at most $C\log m$
times as large as the minimum one, for a large enough constant $C>0$.
Despite extensive work conducted on Hitting Set in the last decades, a gap
remains in our understanding of the typical performance of linear programming
and the greedy algorithm on random problem instances. We hence pose the
following questions:

  1. (1)

For which regimes of $m,n,p$ are there (multiplicative) integrality gaps in
random instances of Hitting Set?

  2. (2)

What is the average case performance of the greedy algorithm with respect to a
chosen input distribution?

In the present work, we provide answers to the above questions _with high
probability_ (w.h.p.) in a non-asymptotic sense, in the setting where the
cardinality $n$ of the ground set $\mathcal{X}$ is large but finite. We will
prove the absence of integrality gaps in a wide regime of $n,m,p$, by
conducting an average case analysis of an algorithm that outputs integral
covers of matching size to the fractional ones. In addition, a rigorous
analysis of the greedy routine will follow by a straightforward reduction. The
forthcoming results are valid under the conditions listed below, which will be
assumed to hold throughout.

######  Assumption 1.

We assume that

  1. (1.1)

Each element $j\in\mathcal{X}$ is assigned to any subset $\mathcal{S}_{i}$,
$i\in[m]$ with probability $p\equiv p(n)$, independently. That is,
${\boldsymbol{A}}\in\\{0,1\\}^{m\times n}$ is such that
$A_{ij}\overset{\text{iid}}{\sim}\mathrm{Bernoulli}(p)$;

  2. (1.2)

$n$ is intended to be large but finite;

  3. (1.3)

$m\equiv m(n)=\mathrm{poly}(n)$, i.e. $\exists c,C>0$, such that $cn^{c}\leq
m\leq Cn^{C}$ for $n$ large enough;

  4. (1.4)

There exist $\delta\in(0,1)$, such that $p\equiv p(n)$ satisfies
$1/n^{\delta}\leq p\leq 1/2$, for all $n$ large enough.

Note that in Assumption 1.3, the upper bound is chosen to avoid trivial
solutions w.h.p., which e.g. arise in the setting where the number of sets
grows exponentially in the cardinality of $\mathcal{X}$. In addition,
Assumption 1.4 is by no means restrictive, since one can show that for
$m=\text{poly}(n)$ and $np\ll\log n$, we have that w.h.p., ${\boldsymbol{A}}$
contains an all-zero row, i.e. no feasible solution for IP. The requirement
$p\leq 1/2$ is chosen for technical convenience and can be relaxed to any
constant $p$, encompassing the regime in [8].

Our contributions stem from the study of the size of the inclusion sets
$I_{j}:=\left\\{i\in[m]\>:\>j\in\mathcal{S}_{i}\right\\}$, for $j\in[n]$,
which in the MVCH formulation of the problem at hand correspond to the degrees
of vertices in the underlying hypergraph. The key quantity under scrutiny is
the average inclusion set size, that is ${{\mathbb{E}}}|I_{j}|=mp$, for all
$j$, under the present distributional assumptions. This quantity exhibits two
separate regimes of interest, referred to as the _sparse_ , $mp\ll\log{n}$,
and _dense_ , $mp\gg\log{n}$, regimes. These in turn determine the size of the
maximum inclusion set, or maximum degree,
$d_{\mathtt{max}}:=\max_{j\in[n]}|I_{j}|$. We characterize the integrality gap
behaviour up to multiplicative constants and analyse Lovász’s Greedy algorithm
[10] in these two regimes w.h.p as $n\to\infty$. We do this by proving the
success of a simple greedy heuristic, the BlockGreedy algorithm (Algorithm 2).
Throughout, we use the notation $\text{val}_{\mathtt{Gr}}$, valAlg to denote
the size of the hitting set returned by Greedy and BlockGreedy respectively.
Below we provide an informal description of the main results, also depicted in
Figure 1. The formal statements are given in Theorem 1 and Theorem 2.

####  Sparse Regime ($mp\ll\log{n}$):

We show that there is _no integrality gap_
($\text{val}\textsubscript{{LP}}/\text{val}\textsubscript{{IP}}\sim 1$) in the
sparse regime by proving that the BlockGreedy algorithm succeeds in reaching
the LP lower bound of $\frac{m}{d_{\mathtt{max}}}$.

$\text{val}\textsubscript{{Alg}}\sim\text{val}\textsubscript{{IP}}\sim\text{val}\textsubscript{{LP}}\sim\frac{m}{d_{\mathtt{max}}}.$

####  Dense Regime ($mp\gg\log{n}$):

We prove the existence of a tight, non-vanishing integrality gap between IP
and LP in the dense regime through the first moment method. We show that the
BlockGreedy algorithm performs as well as IP in this regime, i.e.

$\frac{1}{p}\log\left(\frac{mp}{\log
n}\right)\sim\text{val}\textsubscript{{Alg}}\sim\text{val}\textsubscript{{IP}}\gg\text{val}\textsubscript{{LP}}\sim\frac{1}{p}\sim\frac{m}{d_{\mathtt{max}}}.$

####  Threshold Regime ($mp\sim\log{n}$):

This regime smoothly interpolates between the sparse and dense ones, with no
integrality gaps. The scaling for all quantities of interest is
$m/d_{\mathtt{max}}\sim 1/p$.

####  Greedy:

We prove that
$\text{\text{val}\textsubscript{{Gr}}}\sim\text{val}\textsubscript{{IP}}$ for
$\delta<1/2$, where $\delta$ is the parameter from Assumption 1.4.

$n^{0.1}$$n^{0.3}$$n^{0.5}$$n^{0.7}$$1/n^{0.9}$$1/n^{0.7}$$1/n^{0.5}$$1/n^{0.3}$valAlg
$\sim$ valIP $\sim$ valLP $\sim m/d_{\mathtt{max}}$valAlg $\sim$ valIP
$\sim\log\left(\frac{mp}{\log n}\right)/p$valLP $\sim
1/p$$m(n)$$p(n)$$mp\sim\log n$ Figure 1. Transition between the sparse and the
dense regime for different values of the average inclusion set size $mp$.

The rest of the paper is organized as follows. In Section 2, we present
relevant notation. In Section 3, we outline and discuss the relevant
literature. In Section 4, we prove a number of preliminary results that will
be instrumental in developing the core arguments. In Section 5, we study the
value of $d_{\mathtt{max}}$. Subsequently, in Section 6, we delve into the
algorithmic aspects of the problem at hand by first providing guarantees on a
simple algorithm, BlockGreedy. We then analyse Greedy by means of a reduction.
We conclude in Section 7 by summarizing the results and offering indications
for future work. We defer the proofs of more technical results to the
appendix, in order to streamline the presentation for the reader’s
convenience.

##  2\. Notation and conventions

For integers $k\in\mathbb{N}$, we write $[k]:=\left\\{1,...,k\right\\}$. We
denote vectors, matrices by bold-faced Roman letters
$\mathbf{x},{\boldsymbol{A}}\in\mathbb{R}^{k},\mathbb{R}^{k\times k}$,
respectively, for some $k\in\mathbb{N}$. Define the _inclusion set_ of an
element, or node, $j\in[n]$ as
$I_{j}=\left\\{i\in[m]:j\in\mathcal{S}_{i}\right\\}$. We denote the $\ell_{1}$
norm of the $j$-th column of ${\boldsymbol{A}}$ by $X_{j}$, $j\in[n]$, noting
that $X_{j}=|I_{j}|$ and $X_{1},\ldots
X_{n}\overset{\text{iid}}{\sim}\mathrm{Binomial}(m,p)$. In addition, we let
$d_{\mathtt{max}}\equiv
d_{\mathtt{max}}(X_{1},\ldots,X_{n}):=\max_{i\in[n]}X_{i}$. We use
${{\mathbb{E}}},\text{Var}$ to denote expectation and variance, respectively.
By $\lesssim$, $\gtrsim$ we denote inequalities up to constants. We let $A\sim
B$ denote that $A\lesssim B\lesssim A$ for large enough $n$. We let $\log$
denote the natural logarithm.
For possibly random functions $f(n),g(n)$, we let $\\{f\lesssim g\\}$ denote a
sequence of events $\\{f(n)\leq Ag(n)\\}$ for some constant $A>0$ independent
of $n$. Consequently, ${\mathbb{P}}(f\lesssim g)$ is viewed as a function of
$n$. The notation for other inequalities is defined analogously. We say that a
sequence of events $\left\\{A_{n}\right\\}$ holds _with high probability_
(w.h.p.) with respect to a probability measure $\mathbb{P}$ if there exists a
constant $c>0$, independent of $n$, such that $\mathbb{P}(A_{n})\geq
1-n^{-c}$, for large enough values of $n$.

##  3\. Related Work

Perhaps the most well-known algorithm for solving Hitting Set, or equivalently
MVCH, is the greedy algorithm of Lovász [10], with runtime complexity
$O(mn^{2})$. This algorithm, which constructs a cover by sequentially adding
elements of the ground set which hit the largest number of remaining subsets,
was initially studied by Lovász [10] and Johnson [9] independently, for
deterministic hypergraphs. Lovász analyses the greedy algorithm to obtain an
upper bound on the Hitting Set integrality gap of $1+\log d_{\mathtt{max}}$.
However, for many natural examples, the maximum degree grows with the number
of vertices in the hypergraph, leading to progressively worse bounds as the
size increases. Slavik [13] developed the tightest known analysis, showing
that the greedy algorithm is essentially the best-possible polynomial-time
approximation algorithm for set cover, with an approximation ratio of $O(\log
m)$.

Nevertheless, much less is known about the typical performance of polynomial-
time algorithms on random instances of Hitting Set. Closing this gap is
important from a theoretical standpoint and for applications in combinatorial
inference. A prime example of this is found in _group testing_ , a classical
inference problem where one aims to identify a small subset of defective items
within a large population by conducting the smallest number of pooled tests,
with applications ranging from the analysis of communication protocols [6] to
DNA sequencing [4] and search problems [3]. In [8], Iliopulos and Zadik
consider the smallest hitting set as an estimator in the setting of the group
testing problem, referring to it as the _Smallest Satisfying Set_ estimator.
In particular, they provide extensive empirical evidence supporting the claim
that the class of instances of the random hitting set problem induced by non-
adaptive group testing is tractably solvable by computers.
The analysis of a random instance of Hitting Set appears in the work of Mézard
and Tarzia and relies on nonrigorous techniques from statistical physics [11].
This work considers regular uniform hypergraphs, where the degree of vertices
and the size of edges are fixed and assumed to be constant. Depending on these
values, they showed phase transitions between the replica symmetry, 1-replica
symmetry breaking, and full replica symmetry breaking phases, which
characterize the complexity of the optimization landscape for this problem in
the average case setting.
Another instance was studied by Telelis and Zissimopoulos [14] in the setting
of random Bernoulli hypergraphs, where elements belong to subsets
independently with _fixed_ probability $p\in(0,1)$. Their analysis concerns
the asymptotic regime where the size $n$ of the ground set scales to infinity.
In this setting, they study the average-case performance of a simple
deterministic algorithm which approximates random Hitting Set within an
additive error term of order at most $\log m$ almost everywhere. This gives an
improvement over Lovász’s argument in [10], since in this setting
$d_{\mathtt{max}}$ is at most of order $m$. However, the analysis in [14] does
not capture the case of sparse hypergraphs obtained for $p\to 0$ as
$n\to\infty$ and, more broadly, any regime where $p$ scales with the size of
the ground set $n$. The analysis in [14] also does not prove guarantees for
the Greedy algorithm in the chosen parameter regime.
For completeness, we also bring to the reader’s attention a more recent line
of work [1, 2], where the authors obtain bounds on (additive) integrality gaps
between the value of a random integer program
$\max{\boldsymbol{c}}^{T}{\boldsymbol{x}},{\boldsymbol{A}}{\boldsymbol{x}}\leq{\boldsymbol{b}},{\boldsymbol{x}}\in\left\\{0,1\right\\}^{n}$
with $m$ constraints and that of its linear programming relaxation for a wide
range of distributions on
$({\boldsymbol{A}},{\boldsymbol{b}},{\boldsymbol{c}})$, holding w.h.p. as
$n\rightarrow\infty$. These include the case where the entries of
${\boldsymbol{A}}$ are uniformly distributed on an integer interval consisting
of at least three elements and where the columns of ${\boldsymbol{A}}$ are
distributed according to an isotropic logconcave distribution. However, these
fail to capture the setting where ${\boldsymbol{A}}$ is sparse with entries in
$\left\\{0,1\right\\}$, which is of interest for Hitting Set.

##  4\. Bounds on valLP and valIP

The aim of this section is to obtain preliminary bounds on
$\text{val}\textsubscript{{LP}},\text{val}\textsubscript{{IP}}$, starting from
the following deterministic lower bound on valLP, which holds across all
regimes of $m,n,p$.

######  Lemma 1.

We have that

$\text{val}\textsubscript{{LP}}\geq\frac{m}{d_{\mathtt{max}}}.$

###### Proof.

Let
${\boldsymbol{x}}^{*}_{\texttt{LP}}=({\boldsymbol{x}}_{1}^{*},{\boldsymbol{x}}_{2}^{*},\ldots,{\boldsymbol{x}}_{m}^{*})$
be an optimal solution for (1.2). Since
${\boldsymbol{A}}{\boldsymbol{x}}^{*}_{\texttt{LP}}\geq\mathbf{1}$ entrywise,
by summing all entries we obtain that

$m\leq\sum_{i}{\boldsymbol{x}}^{*}_{i}X_{i}\leq
d_{\mathtt{max}}\sum_{i}{\boldsymbol{x}}^{*}_{i}=d_{\mathtt{max}}\text{val}\textsubscript{{LP}}.$

which upon rearranging yields the desired result. ∎

In addition to the above, we have the following elementary upper bound on
valLP, which holds both in the sparse and dense regime.

######  Lemma 2.

There exists $c>0$, independent of $n$, such that

${\mathbb{P}}\left(\text{val}\textsubscript{{LP}}\lesssim\frac{1}{p}\right)\geq
1-\exp\left(-cn^{1-\delta}\right).$

This also implies that ${\mathbb{P}}(\texttt{IP}\text{ is feasible})\geq
1-\exp\left(-cn^{1-\delta}\right).$

###### Proof.

Consider the candidate feasible solution
$\hat{{\boldsymbol{x}}}:=\frac{1}{\tilde{C}np}\mathbf{1}$, for some constant
$0<\tilde{C}<1$. The following results from applying a union bound over
constraints and the standard Chernoff bound.

$\displaystyle{\mathbb{P}}\left(\hat{{\boldsymbol{x}}}\>\text{not
feasible}\right)$ $\displaystyle={\mathbb{P}}\left(\exists
i\in[m]:\left({\boldsymbol{A}}\hat{{\boldsymbol{x}}}\right)_{i}<1\right)$
$\displaystyle\leq m{\mathbb{P}}\left(\text{Bin}(n,p)<\tilde{C}np\right)$
$\displaystyle\leq n^{C}\exp\left(-\frac{(1-\tilde{C})^{2}np}{2}\right)$
$\displaystyle\leq\exp\left(-cn^{1-\delta}\right).$

The desired conclusion follows by considering the complementary event to the
one above and noting that $\left\|\hat{{\boldsymbol{x}}}\right\|_{1}\sim 1/p$.
Note that the event $\\{\hat{{\boldsymbol{x}}}\text{ is feasible for
}\texttt{LP}\\}$ implies the event $\\{\texttt{IP}\text{ is feasible}\\}$. ∎

Lemma 1 clearly implies that $\text{val}\textsubscript{{IP}}\geq
m/d_{\mathtt{max}}$. However, when $mp\gg\log n$, this lower bound is not
precise. Indeed, we will apply the first moment method to prove a tighter
lower bound on valIP. We first recall the following properties of the Lambert
$W$ function, which consists of the solution to the equation $ye^{y}=x$, for
$x\geq 0$.

######  Lemma 3 (Lambert $W$ function, [7]).

For any $x\geq e$, there holds that

(4.1) $\displaystyle\log x-\log\log x+\frac{\log\log x}{2\log x}\leq
W_{0}(x)\leq\log x-\log\log x+\frac{e}{e-1}\frac{\log\log x}{\log x}.$

In particular,

(4.2) $\displaystyle W_{0}(x)=\log x-\log\log x+o(1),\quad\text{as}\quad
x\rightarrow\infty.$

In addition, for any $x\geq 1/e$, the following identity is satisfied

(4.3) $\displaystyle W_{0}(x)=\log\frac{x}{W_{0}(x)}.$

We now provide a tighter lower bound for valIP in the regime $mp\gg\log{n}$
through the first moment method.

######  Lemma 4.

If $mp\gg\log n$, we have that, for any $D\geq 1$, for $n$ large enough,

${\mathbb{P}}\left(\text{val}\textsubscript{{IP}}\gtrsim\frac{1}{p}\log\left(\frac{mp}{\log
n}\right)\right)\geq 1-n^{-D}.$

###### Proof of Lemma 4.

Fix $D\geq 1$. Let
$Z_{k}:=\lvert\left\\{{\boldsymbol{x}}\in\left\\{0,1\right\\}^{m}:{\boldsymbol{A}}{\boldsymbol{x}}\geq\mathbf{1},\|{\boldsymbol{x}}\|_{1}=k\right\\}\rvert$
be the number of feasible solutions of norm exactly $k$. Clearly, $Z_{k}\leq
Z_{k+1}$ for any $k\geq 0$. We also have that

$\displaystyle\mathbb{E}Z_{k}$
$\displaystyle=\sum_{\|{\boldsymbol{x}}\|=k}{\mathbb{P}}\left({({\boldsymbol{A}}{\boldsymbol{x}})_{i}\geq
1,\forall i\in[m]}\right)=\binom{n}{k}\left(1-(1-p)^{k}\right)^{m}.$

We will now show that for $k\ll\frac{1}{p}\log\left(\frac{mp}{\log n}\right)$,
we have $\mathbb{E}Z_{k}\leq n^{-D}$. Using that $p\leq 1/2$ from Assumption
1.4 and that for $x\in(0,\frac{1}{2})$, we have $(1-x)^{y}\geq e^{-2xy}$, we
can bound

$\displaystyle\mathbb{E}Z_{k}$
$\displaystyle=\binom{n}{k}(1-(1-p)^{k})^{m}\leq
n^{k}\left(1-e^{-2pk}\right)^{m}$ $\displaystyle\leq
n^{k}e^{-me^{-2pk}}=\exp\left\\{k\log n-me^{-2pk}\right\\}.$

Therefore, $\mathbb{E}Z_{k}\leq n^{-D}$ will follow from

(4.4) $2pke^{2pk}\leq-2Dpe^{2pk}+\frac{2mp}{\log n}.$

Since $k\ll\frac{1}{p}\log\left(\frac{mp}{\log n}\right)$, we also have that
$k\leq k_{\ast}\coloneqq\frac{1}{2p}W_{0}\left(\frac{mp}{D\log n}\right)$ for
$n$ large enough. For $k=k_{\ast}$, the left hand side of (4.4) is equal to
$\frac{mp}{D\log n}$, while the right hand side is lower bounded by
$\frac{mp}{\log n}$. Since $D\geq 1$, we recover that $\mathbb{E}Z_{k}\leq
n^{-D}$. Note that for $n$ large enough,
$\text{val}\textsubscript{{IP}}\ll\frac{1}{p}\log\frac{mp}{\log n}$ implies
that $Z_{k_{\ast}}>0$. Therefore, applying Markov’s inequality, we get that

(4.5)
$\displaystyle{\mathbb{P}}\left(\text{val}\textsubscript{{IP}}\ll\frac{1}{p}\log\left(\frac{mp}{\log
n}\right)\right)\leq{\mathbb{P}}\left(Z_{k_{\ast}}>0\right)\leq\mathbb{E}Z_{k_{\ast}}\leq
n^{-D},$

and the proof follows by considering the complementary events. Note that using
similar derivations, one can also show that for
$k^{\ast}\coloneqq\frac{1}{p}\log\left(\frac{1}{\delta}\frac{mp}{\log
n}\right)$, where $\delta$ is defined in Assumption 1.4, we have
$\mathbb{E}Z_{k^{\ast}}\geq 1$. ∎

##  5\. Analysis of $d_{\mathtt{max}}$

In this section we will first estimate the size of
${{\mathbb{E}}}d_{\mathtt{max}}$ and subsequently show that w.h.p.
$d_{\mathtt{max}}\lesssim{{\mathbb{E}}}d_{\mathtt{max}}$, which suffices for
the purposes of this work. For additional arguments concerning concentration
of $d_{\mathtt{max}}$ around its mean, we refer the reader to Lemmas 11, 10.
In order to deal with the more delicate sparse regime where $mp\ll\log n$, we
state the following technical lemma, whose proof is presented in Appendix B.

######  Lemma 5.

For $mp\ll\log{n}$, $\varepsilon>0$, and $n$ large enough, we have

${\mathbb{P}}\left(\mathrm{Bin}(m,p)=\left\lceil{\frac{\varepsilon}{8}\frac{\log{n}}{\log\left(\log
n/mp\right)}}\right\rceil\right)\geq n^{-\varepsilon}.$

We proceed to estimate $\mathbb{E}d_{\mathtt{max}}$, by differentiating the
sparse and dense regimes for the average inclusion set size. The following
lemma characterizes the two distinct regimes of the maximum inclusion set size
$\max_{j\in[n]}|I_{j}|$.

######  Lemma 6 (Maximum of Binomials).

Let $X_{1},\ldots,X_{n}\overset{\underset{\mathrm{iid}}{}}{\sim}Bin(m,p)$.
Under the conditions in Assumption 1, it holds that

$\displaystyle\mathbb{E}d_{\mathtt{max}}=\mathbb{E}\max_{i\in[n]}X_{i}\sim\begin{cases}\frac{\log{n}}{\log\left(\log
n/mp\right)}&\text{, if }mp\ll\log{n},\\\ mp&\text{, if
}mp\gtrsim\log{n}.\end{cases}$

###### Proof.

For ease of notation, let us define $b_{n}:=\frac{\log
n}{mp},\>b_{n}^{*}:=\frac{1}{e}\left(b_{n}-1\right)$,
$g_{n}:=\frac{\log{n}}{\log\left(\log n/mp\right)}$. We begin by proving the
desired upper bound. By Jensen’s inequality and bounding the maximum of
positive values by their sum, for any $\lambda>0$, we obtain

$\displaystyle\mathbb{E}\max_{i\in[n]}X_{i}$
$\displaystyle\leq\frac{1}{\lambda}\log\mathbb{E}\exp\left(\lambda\max_{i\in[n]}X_{i}\right)=\frac{1}{\lambda}\log\mathbb{E}\left(\max_{i\in[n]}\exp\left(\lambda
X_{i}\right)\right)\leq\frac{1}{\lambda}\log\sum_{i\in[n]}\mathbb{E}\exp(\lambda
X_{i}).$

Finally, computing the moment generating function of binomial random
variables, together with the inequality $1-x\leq e^{-x}$ yields

$\displaystyle\mathbb{E}\max_{i\in[n]}X_{i}=\frac{\log{n}+m\log{(1-p(1-e^{\lambda}))}}{\lambda}\leq\frac{\log{n}-mp(1-e^{\lambda})}{\lambda}.$

In the regime where $mp\gtrsim\log n$, we may choose $\lambda>0$ arbitrary,
independent of $n$, from which it immediately follows that
${{\mathbb{E}}}\max_{i\in[n]}X_{i}\lesssim mp$.
For $mp\ll\log n$, we proceed by differentiating the last line in the above
display and setting the resulting expression to zero. From this, we may choose
$\lambda$ as the solution of the following.

$e^{\lambda-1}\left(\lambda-1\right)=b_{n}^{*}$

Under the present assumptions, this is expressed in terms of the Lambert W
function as $\lambda=1+W_{0}(b_{n}^{*})$, so that by (4.3), we obtain

$\displaystyle{{\mathbb{E}}}\max_{i\in[n]}X_{i}\leq\frac{\log
n\left(1-\frac{1}{b_{n}}+\frac{b_{n}^{*}}{b_{n}}\frac{e}{W_{0}(b_{n}^{*})}\right)}{1+W_{0}(b_{n}^{*})}\sim
g_{n}.$

In the dense $mp\gtrsim\log{n}$ regime, a matching lower bound is easily
obtained by noting that
${{\mathbb{E}}}\max_{i\in[n]}X_{i}\geq{{\mathbb{E}}}X_{1}=mp$.
To deal with the sparse regime, let $\tau=1/16$. From Markov’s inequality,

$\displaystyle\mathbb{E}\max_{i\in[n]}X_{i}$ $\displaystyle\geq\tau
g_{n}{\mathbb{P}}\left(\max_{i\in[n]}X_{i}=\lceil\tau g_{n}\rceil\right)=\tau
g_{n}\left(1-\left(1-{\mathbb{P}}\left(X_{1}=\lceil\tau
g_{n}\rceil\right)\right)^{n}\right).$

Hence, applying Lemma 5, for $n$ large enough,

$\displaystyle\mathbb{E}\max_{i\in[n]}X_{i}\geq\tau
g_{n}\left(1-\left(1-n^{-1/2}\right)^{n}\right)\geq(\tau/2)g_{n},$

thus providing a matching lower bound for the sparse regime. ∎

######  Remark 1.

We note that in the sparse regime $mp\ll\log n$, there holds that
$mp\ll\mathbb{E}d_{\mathtt{max}}\ll\log n$, whereas in the dense regime
$mp\gg\log n$, we have that $mp\sim\mathbb{E}d_{\mathtt{max}}\gg\log n$. In
the threshold regime $mp\sim\log n$, the average and maximum of $X_{i}$’s
become of the same order, that is $mp\sim\mathbb{E}d_{\mathtt{max}}\sim\log
n$. The smooth transition is visible from the proof by noting that in this
regime, $b_{n},b_{n}^{*},W_{0}(b_{n}^{*})\sim 1$.

We conclude this section by bounding $d_{\mathtt{max}}$ by its expectation
from above, up to multiplicative constants w.h.p.. Whilst this one sided
result suffices for the forthcoming analysis, we expect a matching lower bound
to hold as well. Additional insights into the concentration of
$d_{\mathtt{max}}$ may be found in Lemmas 10, 11, in Appendix A.

######  Lemma 7.

Let $X_{1},\ldots,X_{n}\overset{\underset{\mathrm{iid}}{}}{\sim}Bin(m,p)$.
Then, there exist constants $c,\tilde{c}>0$, independent of $n$, such that

${\mathbb{P}}\left(\max_{i\in[n]}X_{i}\geq
c\cdot{{\mathbb{E}}}\max_{i\in[n]}X_{i}\right)\leq\frac{1}{n^{\tilde{c}}}$

That is, $\max_{i\in[n]}X_{i}\lesssim{{\mathbb{E}}}\max_{i\in[n]}X_{i}$
w.h.p..

###### Proof.

Let us consider the sparse and dense regimes separately.
In the dense regime for $mp\gtrsim\log n$, there exist constants
$c_{1},c_{2},c_{3}>0$ such that
$c_{1}mp\leq{{\mathbb{E}}}\max_{i\in[n]}X_{i}\leq c_{2}mp$, as argued in Lemma
6, and $mp\geq c_{3}\log n$. We apply the union and Chernoff bounds as in
Lemma 9 to obtain, for any $t\geq 1/c_{1}$,

$\displaystyle{\mathbb{P}}\left(\max_{i\in[n]}X_{i}\geq
t\cdot{{\mathbb{E}}}\max_{i\in[n]}X_{i}\right)$ $\displaystyle\leq
n{\mathbb{P}}\left(X_{1}\geq tc_{1}mp\right)$ $\displaystyle\leq
n\exp\left(-\frac{(tc_{1}-1)^{2}mp}{1+tc_{1}}\right)$ $\displaystyle\leq
n\exp\left(-\frac{c_{3}(tc_{1}-1)^{2}\log n}{1+tc_{1}}\right).$

It now suffices to choose $t$ as a function of $c_{1},c_{3}$ such that
$\frac{c_{3}(tc_{1}-1)^{2}}{1+tc_{1}}>1$. By rearranging and solving the
resulting quadratic equation, it follows immediately that any
$t>\frac{1}{c_{1}}+\frac{1+\sqrt{1+8c_{3}}}{2c_{3}c_{1}}>\frac{1}{c_{1}}$
suffices. Hence, there exist universal constants $c,\tilde{c}$, such that the
desired conclusion holds.
We now consider the sparse regime $mp\ll\log n$, where by Lemma 6 there exists
$c_{4}>0$ such that $mp\leq c_{4}\log n/\log\left(\frac{\log n}{\log
mp}\right)$. Notice that for any $\lambda>0$,
$\max_{i\in[n]}X_{i}\leq\frac{1}{\lambda}\log\sum_{i=1}^{n}e^{\lambda X_{i}}$.
We apply Markov’s inequality to obtain, for any $t>0$,

$\displaystyle{\mathbb{P}}\left(\max_{i\in[n]}X_{i}\geq
t\cdot{{\mathbb{E}}}\max_{i\in[n]}X_{i}\right)$
$\displaystyle\leq{\mathbb{P}}\left(\sum_{i=i}^{n}e^{\lambda X_{i}}\geq
e^{\lambda t{{\mathbb{E}}}\max_{i\in[n]}X_{i}}\right)$
$\displaystyle\leq\frac{n{{\mathbb{E}}}e^{\lambda X_{1}}}{\exp\left(\lambda
t\>{{\mathbb{E}}}\max_{i\in[n]}X_{i}\right)}$
$\displaystyle=\frac{n\left(1-p+pe^{\lambda}\right)^{m}}{\exp\left(\lambda
t\>{{\mathbb{E}}}\max_{i\in[n]}X_{i}\right)}$ $\displaystyle\leq\exp\left(\log
n+mp\left(e^{\lambda}-1\right)-\frac{\lambda t\>c_{4}\log
n}{\log\left(\frac{\log n}{mp}\right)}\right),$

where we used that $1+x<e^{x}$ to obtain the last inequality. Finally, by
choosing $t=3/c_{4}$ and $\lambda=\log\left(\log n/mp\right)$, we obtain

$\displaystyle{\mathbb{P}}\left(\max_{i\in[n]}X_{i}\geq\frac{3}{c_{4}}\cdot{{\mathbb{E}}}\max_{i\in[n]}X_{i}\right)\leq\frac{1}{n}.$

∎

##  6\. Algorithmic solutions

Algorithm 1 Greedy

1:$\mathcal{I}\leftarrow\\{I_{1},\ldots,I_{n}\\}$ $\triangleright$ Inclusion
sets

2:$U\leftarrow[m]$

3:$t\leftarrow 0$

4:while $|U|>0$ do

5: $P\leftarrow\mathrm{argmax}_{I\in\mathcal{I}}\bigl{|}I\cap U\bigr{|}$
$\triangleright$ Greedy step

6: $\mathcal{I}\leftarrow\mathcal{I}\setminus\\{P\\}$

7: $U\leftarrow U\setminus P$

8: $t\leftarrow t+1$

9:$\text{\text{val}\textsubscript{{Gr}}}\leftarrow t$

10:return valGr.

The aim of the present section is to conduct a rigorous analysis of the
standard Greedy algorithm for the hitting set problem, within the prescribed
Bernoulli random setting. In particular, we show that this routine succeeds at
constructing hitting sets of optimal size w.h.p., as in the results of Section
4, up to multiplicative constants. This is done by first analysing a variation
of the greedy heuristic, and subsequently proceeding by a reduction argument.
The core principle of Greedy is to construct a feasible solution in steps, by
sequentially adding to the candidate solution an element which hits the
largest number of remaining sets. In the chosen setting, where elements are
added to sets with equal probability and independent of each other, we have
precise estimates on the number of subsets hit by an element which is picked
first. In fact, the size of this set is given by the maximum of independent
Binomial random variables, which was analysed in Section 5. However, this very
first step introduces nontrivial dependencies amongst the remaining matrix
columns and significantly complicates keeping track of the marginal gains of
each subsequent element addition to the candidate solution.
In order to circumvent this issue, we introduce a modified greedy routine,
which we refer to as BlockGreedy algorithm, where the elements of the ground
set $[n]$ are split into separate sets, which we call blocks. At the $t$-th
iteration, the algorithm picks the largest column from the first $t$ blocks
only. By choosing the number of blocks appropriately, one is guaranteed to
find enough independent columns at each iteration, whilst finding a solution
of optimal size. Also, the additional block constraint allows us to analyse
how many subsets are hit by each chosen element, not just the first one, by
still relying on fundamental properties of independent Binomial random
variables.
BlockGreedy is detailed in Algorithm 2, whilst informally, it works as
follows.

  1. (1)

Let $K$ be the size of the solution (suggested by theoretical analysis);

  2. (2)

Uniformly at random split $n$ columns into $K$ blocks with $n/K$ columns per
block;

  3. (3)

Start with an empty set of possible choices of columns;

  4. (4)

At the $t$-th iteration, first add the columns from the $t$-th block (Step 6).
Then, perform one greedy step on the current set of possible choices (Step 7);

  5. (5)

If after $K$ iterations of the algorithm, some subsets remain uncovered, we
use a trivial covering, i.e., covering each subset by a separate column. This
can be done with high probability.

Let $v_{t}$ be the element which is picked at the $t$-th step of BlockGreedy,
$b_{t}$ be the number of new subsets that are hit by $v_{t}$, and
$B_{t}\coloneqq\sum_{i=1}^{t}b_{i}$ be the total number of subsets which are
hit after $t$ steps. In order to analyse how many elements BlockGreedy has
picked, we will introduce the sequence $f_{1},f_{2},\ldots,f_{s}$, with
$F_{t}\coloneqq\sum_{i=1}^{t}f_{i}$, such that the following holds:

  1. (1)

for each $t\leq s$, we have $F_{t}\leq B_{t}$, w.h.p.;

  2. (2)

$F_{s}=m$;

  3. (3)

if $mp\lesssim\log n$, then $s\lesssim\text{val}\textsubscript{{LP}}$,
otherwise, $s\lesssim\text{val}\textsubscript{{IP}}$.

The first and second properties ensure that BlockGreedy picks at most $s$
elements, and the last property gives optimal bounds on $s$. One way to
guarantee that BlockGreedy succeeds is to prove that among the choices of
BlockGreedy at each step $t$, there was an element $\tilde{v}_{t}$ which hits
at least $f_{t}$ new subsets w.h.p. We will prove that it is enough to look
for $\tilde{v}_{t}$ in the new block of columns $\mathcal{B}_{t}$, which are
added at step $t$. Note that unless $F_{t}=m$, we have that $f_{t}\geq 1$,
since each subset is hit by at least one element w.h.p.. Therefore, it will be
enough to find a sequence $\\{f_{1},f_{2},\dots,f_{v}\\}$ such that $F_{v}\geq
m-v$, since it implies $F_{2v}=m$. This allows us to reduce the problem of
proving the effectiveness of BlockGreedy to a key technical lemma. This lemma
assumes that before step $t$, exactly $F_{t-1}$ subsets are hit, and bounds
from below the probability that some vertex in the new bucket will hit at
least $f_{t}$ new subsets. This boils down to computing
${\mathbb{P}}(\mathrm{Bin}(m-F_{t-1},p)\geq f_{t})$.

Algorithm 2 BlockGreedy

1:Let $\mathcal{B}_{t}\subset\left\\{I_{1},...,I_{n}\right\\}$ denote the
$t$-th block, i.e. the inclusion sets that become available at step $t$.

2:$\mathcal{I}\leftarrow\varnothing$

3:$U\leftarrow[m]$

4:$t\leftarrow 0$

5:while $|U|>0$ and $\mathcal{B}_{t}\neq\varnothing$ do

6: $\mathcal{I}\leftarrow\mathcal{I}\cup\mathcal{B}_{t}$ $\triangleright$
Adding elements from the new block

7: $P\leftarrow\mathrm{argmax}_{I\in\mathcal{I}}\bigl{|}I\cap U\bigr{|}$
$\triangleright$ Greedy step

8: $\mathcal{I}\leftarrow\mathcal{I}\setminus\\{P\\}$

9: $U\leftarrow U\setminus P$

10: $t\leftarrow t+1$

11:$\text{val}\textsubscript{{Alg}}\ \leftarrow t$

12:if $|U|>0$ then cover the rest of $U$ with a trivial algorithm,
$\text{val}\textsubscript{{Alg}}\leftarrow\text{val}\textsubscript{{Alg}}+|U|$

13:return valAlg.

######  Lemma 8.

Let $\varepsilon>0$. Consider the following choices of $f_{1},f_{2},\ldots$:

$\displaystyle(i)\quad\text{if }mp\lesssim\log n,\text{ for some constants
}\tau>0\text{ and }1<\alpha<\beta,$ $\displaystyle\qquad\qquad
f_{t}=\left\lceil\left(\alpha/\beta\right)^{k}\tau\mathbb{E}d_{\mathtt{max}}\right\rceil\qquad\text{where
}k\text{ is such that}\quad\beta^{-k-1}m<m-F_{t-1}\leq\beta^{-k}m;$
$\displaystyle(ii)\quad\text{if }mp\gg\log n,\ \text{and }\ \log mp\ll\log n,$
$\displaystyle\qquad\qquad f_{t}=\left\lceil
mp(1-p)^{t-1}\right\rceil\quad\text{if}\quad t\leq
t^{*}\coloneqq\left\lceil\frac{1}{p}\log\left(\frac{mp}{\log
n}\right)\right\rceil,$ $\displaystyle\qquad\qquad
f_{t}=\tilde{f}_{t-t^{*}},\quad\text{otherwise, where }\tilde{f}_{t}\text{ is
the sequence from the case }mp\lesssim\log n;$
$\displaystyle(iii)\quad\text{otherwise, i.e., when }\log mp\gtrsim\log n,$
$\displaystyle\qquad\qquad f_{t}=\left\lceil mp(1-p)^{t-1}\right\rceil.$

Then, there exists $K$, such that

(6.1) $\displaystyle(i)\qquad$ $\displaystyle F_{K}\geq m-K;$
$\displaystyle(ii)\qquad$ $\displaystyle\text{if }mp\lesssim\log n,$
$\displaystyle\text{ then }K\sim\text{val}\textsubscript{{LP}};$
$\displaystyle\text{if }mp\gg\log n,$ $\displaystyle\text{ then
}K\sim\text{val}\textsubscript{{IP}}.$

Furthermore, for this sequence $f_{t}$ (which depends on $\varepsilon$), for
any $t\leq K$,

(6.2) ${\mathbb{P}}(\mathrm{Bin}(m-F_{t-1},p)\geq f_{t})\geq
n^{-\varepsilon}.$

Note that the implicit constants in the statements
$K\sim\text{val}\textsubscript{{LP}}$ or $K\sim\text{val}\textsubscript{{IP}}$
depend on $\varepsilon$.

This lemma highlights the crucial dependency of the problem on the
relationship between the average degree, $mp$, and $\log n$. We comment on the
intuition behind the proof, which can be found in Appendix C. As was shown in
Section 5, $\mathbb{E}d_{\mathtt{max}}$ grows identically to the expected
value whenever the expected value is large ($mp\gtrsim\log n$) and is away
from it otherwise. This is the core property for the proof.

When $mp\sim n^{\gamma}$ for some $\gamma>0$, the analysis is straightforward,
as just picking random columns is good enough (i.e., picking
$f_{t}=\left\lceil mp(1-p)^{t-1}\right\rceil$). More challenging cases arise
when the average degree is close to $\log n$, e.g. $mp=\log^{2}n$ (dense) ,
$mp=\log n$, or $mp=\log n/\log\log n$ (sparse). Here we need to carefully
track how the maximum degree changes. We look for an element which i) covers a
large number of subsets, i.e., close to the expected maximum number,
$\mathbb{E}d_{\mathtt{max}}$ and ii) can be found with large enough
probability. The second property is important for the reduction to the
standard Greedy algorithm, whose direct analysis presents substantial
difficulties, and is done later in this section. The quantity
$\mathbb{E}d_{\mathtt{max}}$ is sensitive to $mp$ whenever the latter is close
to $\log{n}$. Hence, we need to adjust which element we look for accordingly.
This is done by setting
$f_{t}=\left\lceil\left(\alpha/\beta\right)^{k}\tau\mathbb{E}d_{\mathtt{max}}\right\rceil$
and increasing the parameter $k$ as the number of remaining rows, $m-F_{t}$,
decreases.

For example, consider the case $mp=\log^{2}n$. First, we can only pick a
random element, since it will be as good as the maximal element. However,
during the execution of the algorithm, the problem becomes more sparse, and if
we continue to pick random elements, we will construct a suboptimal solution.
Therefore, once we are in the regime $mp\sim\log n$, we start to gradually
increase how much the newly picked element will cover, with respect to a
random element.

It is now straightforward to prove the following theorem, which makes rigorous
the statements in Section 1.

######  Theorem 1.

Under Assumption 1, we have that

(6.3) $\displaystyle(i)\text{ if }\ mp\lesssim\log n\ \text{then, for any
}\varepsilon>0\text{ and }n\text{ large enough},$
$\displaystyle\qquad{\mathbb{P}}\left(\text{val}\textsubscript{{Alg}}\lesssim\frac{m}{\mathbb{E}d_{\mathtt{max}}}\right)\geq
1-\exp\left(-n^{1-\delta-\varepsilon}\right);$ $\displaystyle(ii)\text{ if }\
mp\gg\log n,\text{ then, for any }\varepsilon>0\text{ and }n\text{ large
enough},$
$\displaystyle\qquad{\mathbb{P}}\left(\text{val}\textsubscript{{Alg}}\lesssim\frac{1}{p}\log\left(\frac{mp}{\log
n}\right)\right)\geq 1-\exp\left(-n^{1-\delta-\varepsilon}\right).$

Note that if $mp\gtrsim n^{\gamma}$ for some $\gamma>0$, then
$\log\frac{mp}{\log n}\sim\log n$, and the bound in $(ii)$ can be simplified.

###### Proof.

The main idea of the proof is to analyse the distribution of the columns that
are added at each step $t$. These columns are independent, and for each newly
added column, the number of additional subsets which it covers is distributed
according to $\mathrm{Bin}(m-F_{t-1},p)$, where $F_{t-1}$ is the number of
subsets which are already covered. Lemma 8 allows us to lower bound $F_{t}$,
and we show now that we can do this with high probability.

Fix $\varepsilon>0$ and let $\varepsilon^{\prime}\coloneqq\varepsilon/4$. Let
$f_{1},f_{2},\ldots$ be the sequence from Lemma 8 for $\varepsilon^{\prime}$
and $K$ be the value for which (6.1) is satisfied, i.e. $F_{K}\geq m-K$.
Notice that $K\leq
C\max\left\\{\frac{m}{{{\mathbb{E}}}d_{\mathtt{max}}},\frac{1}{p}\log(\frac{mp}{\log{n}})\right\\}$
for some constant $C>0$, for $n$ large enough. We uniformly at random split
$n$ elements (columns) into $K$ groups of size $n/K$ each (assuming without
loss of generality that $K$ divides $n$, otherwise we consider groups of size
$\left\lfloor n/K\right\rfloor$), so that $\mathcal{B}_{t}$ yields a new set
of $n/K$ elements at each iteration $t\leq K$ and
$\mathcal{B}_{t}=\varnothing$ for $t>K$. We say that the algorithm fails at
step $t$ if before step $t$, at least $m-F_{t-1}$ subsets are covered, but
after step $t$ less than $m-F_{t}$ sets are covered. Using that, for $n$ large
enough, $(i)$ columns in each newly added block are independent, $(ii)$
${\mathbb{P}}\left(\mathrm{Bin}(m-F_{t-1},p)\geq f_{t}\right)\geq
n^{-\varepsilon^{\prime}}$, and $(iii)$ $n/K\geq
n^{1-\delta-\varepsilon^{\prime}}$, we get

$\displaystyle{\mathbb{P}}\left(\text{{BlockGreedy} fails at step t}\right)$
$\displaystyle\overset{(i)}{\leq}\left({\mathbb{P}}\left(\mathrm{Bin}(m-F_{t-1},p)<f_{t}\right)\right)^{n/K}$
$\displaystyle\overset{(ii)}{\leq}\left(1-n^{-\varepsilon^{\prime}}\right)^{n/K}$
$\displaystyle\overset{(iii)}{\leq}\exp\left(-n^{1-\delta-2\varepsilon^{\prime}}\right).$

We then proceed by applying a union bound to obtain the result,

$\displaystyle{\mathbb{P}}\left(\texttt{BlockGreedy}\text{ fails during first
}K\text{ steps}\right)$
$\displaystyle\leq\sum_{t=1}^{K}{\mathbb{P}}\left(\texttt{BlockGreedy}\text{
fails at step t}\right)$ $\displaystyle\leq
K\cdot\exp\left(-n^{1-\delta-2\varepsilon^{\prime}}\right)$
$\displaystyle\leq\exp\left(-n^{1-\delta-3\varepsilon^{\prime}}\right),$

where the second inequality holds since, by definition, the algorithm runs for
$K$ iterations, and the third one holds for $n$ large enough. We proved that
BlockGreedy succeeds in finding at most $K$ elements such that at most
$m-F_{K}$ sets remain uncovered. Since by construction, $m-F_{K}\leq K$, we
can cover the remaining rows trivially using that IP is feasible by Lemma 2
with high probability, which proves that

${\mathbb{P}}\left(\text{val}\textsubscript{{Alg}}\leq 2K\right)\geq
1-\exp\left(-n^{1-\delta-4\varepsilon^{\prime}}\right)=1-\exp\left(-n^{1-\delta-\varepsilon}\right),$

for $n$ large enough. Recalling that $K\lesssim\text{val}\textsubscript{{LP}}$
for $mp\lesssim\log n$, and that $K\lesssim\text{val}\textsubscript{{IP}}$ for
$mp\gg\log n$, finishes the proof. ∎

With the above results at hand, we now proceed to analyse the Greedy algorithm
by means of a suitable reduction. Recall that we denote outputs of BlockGreedy
and Greedy as valAlg and valGr respectively.

######  Theorem 2.

Under Assumption 1 with $\delta<1/2$, we have that, for $n$ large enough,

${\mathbb{P}}\left(\text{\text{val}\textsubscript{{Gr}}}\sim\text{val}\textsubscript{{IP}}\right)\geq
1-\exp\left(-\sqrt{n}\right).$

###### Proof.

We use Theorem 1 with $\varepsilon=1/8-\delta/4$, and let $K,\mathcal{B}_{t}$
be as defined in the proof of Theorem 1. We have that, for $n$ large enough,

$\displaystyle{\mathbb{P}}\left(\texttt{BlockGreedy}\text{ fails at any
step}\right)\leq\exp\left(-n^{\Delta}\right),$

where $\Delta\coloneqq 3/4-\delta/2>1/2$.

Given a matrix ${\boldsymbol{A}}$, consider running the above definition of
BlockGreedy for $J:=\exp(\sqrt{n})$ times, each time reshuffling the columns.
Both valAlg and valGr are random variables, but conditioned on
${\boldsymbol{A}}$, valGr is deterministic, while valAlg still depends on the
randomness of separating columns into blocks. Using the union bound, we have
that

(6.4)
$\displaystyle{\mathbb{P}}\left(\text{\text{val}\textsubscript{{Gr}}}>2K\right)\leq$
$\displaystyle{\mathbb{P}}\left(\exists\text{ a failed copy of
}\texttt{BlockGreedy}\right)$
$\displaystyle+{\mathbb{P}}\left(\text{val}\textsubscript{{Alg}}<\text{\text{val}\textsubscript{{Gr}}}\text{
over all $J$ copies}\right).$

Applying the union bound again, we can upper bound the first term in (6.4):

(6.5) ${\mathbb{P}}\left(\exists\text{ a failed copy of
{BlockGreedy}}\right)\leq
J\exp\left(-n^{\Delta}\right)=\exp\left(-n^{\Delta}+n^{1/2}\right).$

Now we focus on the second term in (6.4). Let $v_{1},v_{2},\ldots,v_{g}$ be
the ordered sequence of elements picked by Greedy. Let
$M_{t}\coloneqq\\{v_{1}\in\mathcal{B}_{1},v_{2}\in\mathcal{B}_{1}\cup\mathcal{B}_{2},\ldots,v_{t}\in\mathcal{B}_{1}\cup\ldots\cup\mathcal{B}_{t}\\}$.
The event
$\\{\text{val}\textsubscript{{Alg}}\geq\text{\text{val}\textsubscript{{Gr}}}\\}$
contains the event $M_{g}$, since in this case BlockGreedy will necessarily
pick exactly the same columns $v_{1},v_{2},\ldots,v_{g}$. Given that each
reshuffling of the columns generates a uniform distribution of
$\mathcal{B}_{i}$’s over possible partitions of $n$ columns, we get that

$\displaystyle{\mathbb{P}}\left(M_{g}\right)={\mathbb{P}}\left(v_{1}\in\mathcal{B}_{1}\right){\mathbb{P}}\left(v_{2}\in\mathcal{B}_{1}\cup\mathcal{B}_{2}\mid
M_{1}\right)\ldots{\mathbb{P}}\left({\boldsymbol{v}}_{g}\in\mathcal{B}_{1}\cup\ldots\cup\mathcal{B}_{g}\mid
M_{g-1}\right).$

The $t$-th term in the product above is equal to

${\mathbb{P}}({\boldsymbol{v}}_{t}\in\mathcal{B}_{1}\cup\ldots\cup\mathcal{B}_{t}\mid
M_{t-1})=\frac{t\frac{n}{K}-(t-1)}{n-(t-1)}\geq\frac{t}{K}-\frac{t-1}{n}\geq\frac{t}{2(K-1)},$

where the last inequality holds for $n\geq 4K$ (recall that $n\gg K$). Since
$M_{g}\subset\\{\text{val}\textsubscript{{Alg}}\geq\text{\text{val}\textsubscript{{Gr}}}\\}$,
we can lower bound the probability of the latter event as follows (note that
when $g<K$ there will be less terms in the product, hence,
${\mathbb{P}}(M_{g})$ will be even larger),

$\displaystyle{\mathbb{P}}\left(\text{val}\textsubscript{{Alg}}\geq\text{\text{val}\textsubscript{{Gr}}}\text{
for }1\text{
copy}\right)\geq{\mathbb{P}}(M_{g})\geq\prod_{t=1}^{K-1}{\mathbb{P}}({\boldsymbol{v}}_{t}\in\mathcal{B}_{1}\cup\ldots\cup\mathcal{B}_{t}\mid
M_{t-1})\geq\prod_{t=1}^{K-1}\frac{t}{2(K-1)}\geq e^{-2K},$

where we used that $k!\geq(k/e)^{k}$ in the last inequality. Since $K\leq
C\max\left\\{\frac{m}{{{\mathbb{E}}}d_{\mathtt{max}}},\frac{1}{p}\log(\frac{mp}{\log{n}})\right\\}$
and $1/p\leq n^{\delta}$, there exists a constant $\tilde{C}>0$ large enough,
such that $K\leq\tilde{C}n^{\delta}\log n$. Therefore, using independence of
the reshuffling between the copies, we can compute

(6.6)
$\displaystyle{\mathbb{P}}\left(\text{val}\textsubscript{{Alg}}<\text{\text{val}\textsubscript{{Gr}}}\text{
over all $J$ copies}\right)$
$\displaystyle=\left(1-{\mathbb{P}}\left(\text{val}\textsubscript{{Alg}}\geq\text{\text{val}\textsubscript{{Gr}}}\text{
for }1\text{ copy}\right)\right)^{J}$ $\displaystyle\leq(1-e^{-2K})^{J}$
$\displaystyle\leq\exp\left(-e^{\sqrt{n}-2\tilde{C}n^{\delta}\log{n}}\right).$

Combining (6.4), (6.5) and (6.6), we showed that
${\mathbb{P}}\left(\text{\text{val}\textsubscript{{Gr}}}>2K\right)\leq\exp\left(-\sqrt{n}\right)$
for $n$ large enough, which finishes the proof. ∎

######  Remark 2.

We note that the $\delta<1/2$ condition in Theorem 2 is likely not optimal,
and could be relaxed by reducing to BlockGreedy with more carefully chosen
sets $\mathcal{B}_{t}$. In particular, the appropriate set sizes
$|\mathcal{B}_{t}|$ may not be identical across $t\leq K$. The analysis
becomes more technical in this case, and we highlight this as an interesting
open direction.

##  7\. Discussion and Open Questions

Our work characterises multiplicative integrality gaps for the random hitting
set problem. In this section, we discuss the intuition behind our main
results, together with open questions and conjectures.

###  7.1. Summary of our results and proof techniques.

We identified that the nature of integrality gaps depends on the size of the
inclusion set, also viewed as the sparsity of the underlying hypergraph. In
particular, when the average degree of a vertex is small, i.e., when each
element belongs to a small number of subsets, we proved that there exists only
a constant gap between linear and integer program solutions, together with a
simple algorithmic solution. The situation changes when the hypergraph becomes
dense, where we show an increasing integrality gap. This separation stems
mostly from the property of the binomial distribution, where the maximum of
random variables grows identically to the expected value whenever the expected
value is large, but is away from it if $mp\ll\log n$.
In our analysis of BlockGreedy, we track this change of behaviour using a
geometric series, which means that the further we are in the execution of the
algorithm, the larger the ratio between the element we pick and the average
element will be. This picture coincides exactly with how the binomial
distribution will behave if we decrease the average degree: for large
instances, it will look approximately as a Gaussian, but when the average
degree is small, Poisson approximation starts to dominate, the right tail
becomes heavier, and the difference between $d_{\mathtt{max}}$ and $mp$
increases. Our analysis tracks the transition between Gaussian and Poisson-
like behavior.

###  7.2. Multiplicative vs. additive integrality gaps

Our result only concerns multiplicative gaps, but the constants in our
analysis can be large. This might be a consequence of the generality of the
studied problem. For example, if one focuses only on the case of constant $p$,
which immediately implies a very dense instance in our characterization, [14]
proves that a simple algorithm is optimal for approximating the integer
program up to a small additive error. Proving similar upper bounds on the
constant in more general cases is an interesting open problem. Based on
numerical experiments, we formulate the following conjectures.

######  Conjecture 1 (Very sparse).

For $mp\ll 1$,

(7.1)
$\frac{\text{\text{val}\textsubscript{{Gr}}}}{\text{val}\textsubscript{{LP}}}\to
1.$

######  Conjecture 2 (Sparse).

For $1\lesssim mp\ll\log n$,

(7.2)
$\frac{\text{\text{val}\textsubscript{{Gr}}}}{\text{val}\textsubscript{{IP}}}\to
1,\qquad\qquad\frac{\text{val}\textsubscript{{IP}}}{\text{val}\textsubscript{{LP}}}\to
C_{1},$

where $1<C_{1}<1.5$.

######  Conjecture 3 (Dense).

For $mp\gg\log n$,

(7.3)
$\frac{\text{\text{val}\textsubscript{{Gr}}}}{\text{val}\textsubscript{{IP}}}\to
C_{2},$

where $1\leq C_{2}<1.5$.

###  7.3. Analysis of a linear program solution.

One motivation for studying the gaps between the integer and linear programs
together with the solutions of linear programs themselves is to construct a
rounding scheme which converts a fractional solution to an integer one. We
believe this is another interesting direction for future work. In particular,
numerical experiments show that entries which have large value in the
fractional solution have a strong tendency to correspond to elements that are
picked for the integer solution. This supports the claim that a combination of
the greedy and linear programming approach might be fruitful in efficiently
solving Hitting Set. One approach for further study consists of first solving
a linear program, initializing ${\boldsymbol{x}}$ with the largest elements in
the linear solution, and greedily covering the remaining subsets.

##  8\. Acknowledgments

The authors thank Dylan J. Altschuler, Afonso S. Bandeira, Raphaël Barboni,
and Anastasia Kireeva for helpful discussions. DD is supported by ETH AI
Center doctoral fellowship and ETH Foundations of Data Science initiative. GA
is supported by the Cambridge Trust and Invenia Labs. NG is grateful for the
funding received from Elizaveta Rebrova.

## References

  * [1] S. Borst, D. Dadush, S. Huiberts, and S. Tiwari.  On the integrality gap of binary integer programs with gaussian data.  Mathematical Programming, 2022.
  * [2] S. Borst, D. Dadush, and D. Mikulincer.  Integrality gaps for random integer programs via discrepancy.  In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA, 2023.
  * [3] D. Du, F. K. Hwang, and F. Hwang.  Combinatorial group testing and its applications.  World Scientific, 2000.
  * [4] Y. Erlich, A. Gilbert, H. Ngo, A. Rudra, N. Thierry-Mieg, M. Wootters, D. Zielinski, and O. Zuk.  Biological screens from linear codes: theory and tools.  BioRxiv, 2015.
  * [5] W. Feller.  An introduction to probability theory and its applications.  1957\.
  * [6] A. Fernández Anta, M. A. Mosteiro, and J. Ramón Muñoz.  Unbounded contention resolution in multiple-access channels.  Algorithmica, 2013.
  * [7] A. Hoorfar and M. Hassani.  Inequalities on the lambert w function and hyperpower function.  J. Inequal. Pure and Appl. Math, 2008.
  * [8] F. Iliopoulos and I. Zadik.  Group testing and local search: is there a computational-statistical gap?  In Conference on Learning Theory, 2021.
  * [9] D. S. Johnson.  Approximation algorithms for combinatorial problems.  In Proceedings of the fifth annual ACM symposium on Theory of computing, 1973.
  * [10] L. Lovász.  On the ratio of optimal integral and fractional covers.  Discrete mathematics, 1975.
  * [11] M. Mézard and M. Tarzia.  Statistical mechanics of the hitting set problem.  Phys. Rev. E, 2007.
  * [12] V. T. Paschos.  A survey of approximately optimal solutions to some covering and packing problems.  ACM Computing Surveys (CSUR), 1997.
  * [13] P. Slavík.  A tight analysis of the greedy algorithm for set cover.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996.
  * [14] O. A. Telelis and V. Zissimopoulos.  Absolute $\text{O}(\log m)$ error in approximating random set covering: an average case analysis.  Information Processing Letters, 2005.
  * [15] R. Van Handel.  Probability in high dimension.  Lecture notes, 2014.

## Appendix A. Auxiliary lemmas

######  Lemma 9.

(Chernoff Bound - upper tail) Let $X_{1},...,X_{n}$ be independent random
variables taking values in $\left\\{0,1\right\\}$, $X$ denote their sum and
$\mu={{\mathbb{E}}}X$. Then for any $\delta>0$,

$\displaystyle{\mathbb{P}}\left(X\geq(1+\delta)\mu\right)\leq
e^{-\delta^{2}\mu/(2+\delta)}.$

In order to deal with concentration of $d_{\mathtt{max}}$ around its
expectation, we state the following useful result on tensorization of
variance. We introduce notation $\text{Var}_{i}$ and ${{\mathbb{E}}}_{i}$,
where subscript $i$ indicates conditioning on each component of an underlying
random vector, except for the $i$-th one.

######  Lemma 10 (Theorem 2.3, [15]).

Let $X_{1},...,X_{n}$ be independent random variables and for each function
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}$, define

$\text{Var}_{i}f(x_{1},...,x_{n}):=\text{Var}\left(x_{1},...,x_{i-1},X_{i},x_{i+1},...,x_{n}\right).$

Then, there holds that

$\text{Var}\left(f\left(X_{1},...,X_{n}\right)\right)\leq{{\mathbb{E}}}\sum_{i=1}^{n}\text{Var}_{i}f\left(X_{1},...,X_{n}\right)$

######  Lemma 11 (Concentration for $d_{\mathtt{max}}$).

Let $X_{1},\ldots,X_{n}\overset{\underset{\mathrm{iid}}{}}{\sim}Bin(m,p)$.
Then, for any $t>0$,

$\displaystyle{\mathbb{P}}\left(\left|d_{\mathtt{max}}-{{\mathbb{E}}}d_{\mathtt{max}}\right|>t\right)\leq\frac{mp}{t^{2}}.$

######  Remark 3.

Note that in all regimes of $m,p$ satisfying Assumption 1, choosing
$t\sim{{{\mathbb{E}}}d_{\mathtt{max}}}$ is sufficient to deduce from the
previous lemma that $d_{\mathtt{max}}\sim\mathbb{E}d_{\mathtt{max}}$ w.h.p..

###### Proof.

Proceeding by Chebyschev’s inequality, it suffices to show that
$\text{Var}(d_{\mathtt{max}}\leq mp$. By Lemma 10, we have that

$\displaystyle\text{Var}(d_{\mathtt{max}})$
$\displaystyle\leq{{\mathbb{E}}}\sum_{i=1}^{n}{{\mathbb{E}}}_{i}\left(d_{\mathtt{max}}-{{\mathbb{E}}}_{i}d_{\mathtt{max}}\right)^{2}$
$\displaystyle={{\mathbb{E}}}\sum_{i=1}^{n}{{\mathbb{E}}}_{i}\left[\left(d_{\mathtt{max}}-{{\mathbb{E}}}_{i}d_{\mathtt{max}}\right)^{2}\mid
d_{\mathtt{max}}=X_{i}\right]{\mathbb{P}}{d_{\mathtt{max}}=X_{i}}$
$\displaystyle+{{\mathbb{E}}}\sum_{i=1}^{n}{{\mathbb{E}}}_{i}\left[\left(d_{\mathtt{max}}-{{\mathbb{E}}}_{i}d_{\mathtt{max}}\right)^{2}\mid
d_{\mathtt{max}}\neq X_{i}\right]{\mathbb{P}}{d_{\mathtt{max}}\neq X_{i}}$
$\displaystyle=\frac{1}{n}{{\mathbb{E}}}\sum_{i=1}^{n}\text{Var}X_{i}$
$\displaystyle\leq mp,$

which is as required. ∎

######  Lemma 12 (Asymptotic expression for binomial probability mass
function).

Let $a\equiv a(n)$ and $b\equiv b(n)$ be such that

  1. (1)

$1\ll b\ll\sqrt{a}$,

  2. (2)

$p\ll 1$.

If $b\geq Cap$ for $C>1$, then

(8.1) $\log{\mathbb{P}}(\mathrm{Bin}(\left\lceil a\right\rceil,p)=\left\lceil
b\right\rceil)\geq-\left(b\log\frac{b}{ap}-b+ap\right)(1+o(1)),$

If also $b\gg ap$, we have that

(8.2) $\log{\mathbb{P}}(\mathrm{Bin}(\left\lceil a\right\rceil,p)=\left\lceil
b\right\rceil)\geq-\left(b\log\frac{b}{ap}\right)(1+o(1)),$

Furthermore, all bounds remain valid upon replacing $\left\lceil
a\right\rceil$ to $\left\lfloor a\right\rfloor$.

###### Proof.

$\displaystyle{\mathbb{P}}(\mathrm{Bin}(\left\lceil a\right\rceil,p)=\lceil
b\rceil)$ $\displaystyle={\left\lceil a\right\rceil\choose\lceil
b\rceil}p^{\lceil b\rceil}(1-p)^{\left\lceil a\right\rceil-\lceil b\rceil}$
$\displaystyle\overset{(i)}{\geq}\frac{(\left\lceil a\right\rceil
p)^{\left\lceil b\right\rceil}}{4(\left\lceil
b\right\rceil)!}(1-p)^{\left\lceil a\right\rceil-\left\lceil b\right\rceil}$
$\displaystyle\overset{(ii)}{\geq}\frac{1}{\left\lceil
b\right\rceil}\left(\frac{\left\lceil a\right\rceil ep}{\left\lceil
b\right\rceil}\right)^{\left\lceil b\right\rceil}(1-p)^{\left\lceil
a\right\rceil-\left\lceil b\right\rceil}$
$\displaystyle\overset{(iii)}{\geq}\frac{1}{\left\lceil
b\right\rceil}\left(\frac{\left\lceil a\right\rceil ep}{\left\lceil
b\right\rceil}\right)^{\left\lceil b\right\rceil}e^{-\left\lceil a\right\rceil
p}(1-p)^{\left\lceil a\right\rceil p-\left\lceil b\right\rceil},$

where $(i)$ is due to ${n\choose k}\geq\frac{n^{k}}{4k!}$ for $0\leq
k\leq\sqrt{n}$, $(ii)$ is due to $n!\leq\frac{n}{4}(n/e)^{n}$ for $n$ large
enough, and $(iii)$ is due to $(1+x/n)^{n}\geq e^{x}(1-x^{2}/n)$ for $|x|\leq
n$. After taking the logarithm, we get

$\log{\mathbb{P}}(\mathrm{Bin}(\left\lceil a\right\rceil,p)=\lceil
b\rceil)\geq-\left(\left\lceil b\right\rceil\log\frac{\left\lceil
b\right\rceil}{\left\lceil a\right\rceil p}-\left\lceil
b\right\rceil+\left\lceil a\right\rceil p+\log\left\lceil
b\right\rceil-(\left\lceil a\right\rceil p-\left\lceil
b\right\rceil)\log(1-p)\right).$

If $b\geq C\left\lceil a\right\rceil p$ for $C>1$, we have that

$b\log\frac{b}{ap}-b+ap\geq\gamma b\gg 1,\qquad\text{for
}\gamma:=\frac{1}{C}+\log C-1>0.$

Since $b\gg 1$, we have

$\frac{\left\lceil b\right\rceil\log\frac{\left\lceil
b\right\rceil}{\left\lceil a\right\rceil p}-\left\lceil
b\right\rceil+\left\lceil a\right\rceil p}{b\log\frac{b}{ap}-b+ap}=1+o(1).$

Now, since also $\log\left\lceil b\right\rceil\ll b$ and $(\left\lceil
a\right\rceil p-\left\lceil b\right\rceil)\log(1-p)\ll b$ for $p\ll 1$, we
have that

$\log{\mathbb{P}}(\mathrm{Bin}(\left\lceil a\right\rceil,p)=\left\lceil
b\right\rceil)\geq-\left(b\log\frac{b}{ap}-b+ap\right)(1+o(1)).$

If additionally $b\gg ap$, then

$\frac{b\log\frac{b}{ap}-b+ap}{b\log\frac{b}{ap}}=1+o(1),$

and, finally,

$\log{\mathbb{P}}(\mathrm{Bin}(\left\lceil a\right\rceil,p)=\lceil
b\rceil)\geq-\left(b\log\frac{b}{ap}\right)(1+o(1)).$

Under our assumptions, $1\ll b\ll\sqrt{a}$, the same bounds hold for
$\log{\mathbb{P}}(\mathrm{Bin}(\left\lfloor a\right\rfloor,p)=\left\lfloor
b\right\rfloor)$. ∎

######  Lemma 13 (Binomial Monotonicity).

Let $S_{m}\sim\mathrm{Bin}(m,p)$. Then for $r\geq mp$, we have that
${\mathbb{P}}(S_{m}=r+1)\leq{\mathbb{P}}(S_{m}=r)$ and
${\mathbb{P}}(S_{m-1}=r)\leq{\mathbb{P}}(S_{m}=r)$.

###### Proof.

The proof follows a similar argument as that presented in [5].

$\displaystyle\frac{{\mathbb{P}}(S_{m}=r+1)}{{\mathbb{P}}(S_{m}=r)}$
$\displaystyle=\frac{{m\choose r+1}p^{r+1}(1-p)^{m-r-1}}{{m\choose
r}p^{r}(1-p)^{m-r}}$
$\displaystyle=\frac{\frac{m!}{(r+1)!(m-r-1)!}p^{r+1}(1-p)^{m-r-1}}{\frac{m!}{r!(m-r)!}p^{r}(1-p)^{m-r}}$
$\displaystyle=\frac{(m-r)p}{(r+1)(1-p)}\leq 1.$

Similar arguments show that
${\mathbb{P}}(S_{m-1}=r)\leq{\mathbb{P}}(S_{m}=r)$. ∎

## Appendix B. Main tool for the case $mp\lesssim\log n$ and Proof of Lemma 5

######  Lemma 14.

If $mp\lesssim\log n$, then, for any $\varepsilon>0$, there exist constants
$\tau>0$ and $1<\alpha<\beta$, such that, for $k\lesssim\log n$ and for any
$\tilde{m}$, satisfying $\beta^{-k-1}m\leq\tilde{m}\leq\beta^{-k}m$, for all
$n$ large enough,

${\mathbb{P}}\biggl{(}\mathrm{Bin}(\tilde{m},p)=\bigl{\lceil}(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}\bigr{\rceil}\biggr{)}\geq
n^{-\varepsilon}.$

###### Proof.

The proof is essentially a careful application of Lemma 12. Let
$\tau,\alpha,\beta$ be constants to be fixed later and
$\tilde{m}=\left\lfloor\beta^{-k-1}m\right\rfloor$. Depending on whether we
have $mp\ll\log n$ or $mp\sim\log n$, different terms will dominate the
asymptotic expression from Lemma 12.

We start with the case $mp\ll\log n$. From Lemma 6, this implies that
$mp\ll\mathbb{E}d_{\mathtt{max}}\ll\log n$. Here we can fix $\alpha\equiv 2$
and $\beta\equiv 3$. Applying (8.2) for $a=3^{-k-1}m$ and
$b=(2/3)^{k}\tau\mathbb{E}d_{\mathtt{max}}$, we have:

(8.3)
$\log{\mathbb{P}}\biggl{(}\mathrm{Bin}(\tilde{m},p)=\bigl{\lceil}(2/3)^{k}\tau\mathbb{E}d_{\mathtt{max}}\bigr{\rceil}\biggr{)}\geq-(2/3)^{k}\tau\mathbb{E}d_{\mathtt{max}}\log\left(\frac{2^{k}3\tau\mathbb{E}d_{\mathtt{max}}}{mp}\right)(1+o(1))$

Recall that our goal is to show
$\log{\mathbb{P}}\biggl{(}\mathrm{Bin}(\tilde{m},p)=\bigl{\lceil}(2/3)^{k}\tau\mathbb{E}d_{\mathtt{max}}\bigr{\rceil}\biggr{)}\geq-\varepsilon\log
n$. We first show that there exists $\tau>0$ satisfying the following two
inequalities:

(8.4) $\displaystyle(i)\qquad(2/3)^{k}\tau(\log 3+k\log
2)\frac{\mathbb{E}d_{\mathtt{max}}}{\log n}$
$\displaystyle\leq\quad\frac{\varepsilon}{4},$
$\displaystyle(ii)\qquad(2/3)^{k}\tau\frac{\mathbb{E}d_{\mathtt{max}}}{\log
n}\log\left(\frac{\mathbb{E}d_{\mathtt{max}}}{mp}\right)$
$\displaystyle\leq\quad\frac{\varepsilon}{4}.$

Indeed, since $\mathbb{E}d_{\mathtt{max}}\ll\log n$ and $k\ll(3/2)^{k}$,
inequality $(i)$ will be satisfied for any $\tau>0$ for $n$ large enough. For
$(ii)$ we need to use explicit bound for $\mathbb{E}d_{\mathtt{max}}$, in
particular from Lemma 6 we know that there exists $C>0$, such that
$\mathbb{E}d_{\mathtt{max}}\leq C\log n/(\log\log n-\log mp)$ for $n$ large
enough. Plugging this into $(ii)$, we get for $k=0$,

(8.5) $\tau\frac{\mathbb{E}d_{\mathtt{max}}}{\log
n}\log\left(\frac{\mathbb{E}d_{\mathtt{max}}}{mp}\right)\leq\frac{\tau C(\log
C+\log\log n-\log(\log\log n-\log mp)-\log mp)}{\log\log n-\log mp}=\tau
C+o(1).$

For $\tau=\varepsilon/(8C)$, $(ii)$ holds for $k=0$ for $n$ large enough. By
increasing $k$ we only decrease left hand side of $(ii)$, therefore, the same
value of $\tau$ works for any $k\geq 0$.

Finally, by adding $(i)$ and $(ii)$ we showed that, for $n$ large enough,

$\log{\mathbb{P}}\biggl{(}\mathrm{Bin}(\tilde{m},p)=\bigl{\lceil}(\alpha/2)^{k}\tau\mathbb{E}d_{\mathtt{max}}\bigr{\rceil}\biggr{)}\geq-\frac{\varepsilon}{2}\log
n(1+o(1))>-\varepsilon\log n,$

which finishes the proof for the case $mp\ll\log n$.

Now we focus on the case $mp\sim\log n$. Here we apply (8.1) for the values
$a={\beta}^{-k-1}m$ and $b=(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}$
keeping in mind the condition $b\geq Cap$ with $C>1$. We have

$\displaystyle\log{\mathbb{P}}\biggl{(}\mathrm{Bin}(\tilde{m},p)=\bigl{\lceil}(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}\bigr{\rceil}\biggr{)}$
$\displaystyle\quad\geq-\left((\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}\log\left(\frac{\beta\alpha^{k}\tau\mathbb{E}d_{\mathtt{max}}}{mp}\right)-(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}+\beta^{-k-1}mp\right)(1+o(1))$

We pick $\tau=\gamma mp/\mathbb{E}d_{\mathtt{max}}$, for some constant
$\gamma>1$ to be specified later. Note that this way condition for applying
(8.1), $\frac{b}{ap}\geq C>1$, is satisfied since
$\frac{b}{ap}\geq\frac{\tau\mathbb{E}d_{\mathtt{max}}}{mp}=\gamma>1$. This
simplifies the latter expression to the following:

$\displaystyle\log{\mathbb{P}}\biggl{(}\mathrm{Bin}(\tilde{m},p)=\bigl{\lceil}(\alpha/\beta)^{k}\gamma
mp\bigr{\rceil}\biggr{)}$ $\displaystyle\quad\geq-
mp\left((\alpha/\beta)^{k}\gamma\log\bigl{(}\beta\gamma\alpha^{k}\bigr{)}-(\alpha/\beta)^{k}\gamma+\beta^{-k-1}\right)(1+o(1))$

Since in this regime we have $mp\leq D\log n$ for some $D>0$, for $n$ large
enough, it is enough to show

$(\alpha/\beta)^{k}\gamma\log\bigl{(}\beta\gamma\alpha^{k}\bigr{)}-(\alpha/\beta)^{k}\gamma+\beta^{-k-1}\leq\varepsilon/(2D).$

We first show that there exist constants $1<\alpha<\beta$ and $\gamma>1$,
depending on $\varepsilon$ and $D$, satisfying the following two inequalities
for any $k\geq 0$:

$\displaystyle(i)\qquad(\alpha/\beta)^{k}\left(\gamma\log\beta\gamma-\gamma+\frac{1}{\alpha^{k}\beta}\right)$
$\displaystyle\leq\quad\frac{\varepsilon}{4D},$
$\displaystyle(ii)\qquad(\alpha/\beta)^{k}k\log\alpha$
$\displaystyle\leq\quad\frac{\varepsilon}{4D}.$

Note that left hand side of $(i)$ decreases as $k$ increases, therefore, it is
enough to look at $k=0$. We need to show that there exist $\beta,\gamma>1$,
depending on $\varepsilon,D$ such that

$f(\beta,\gamma):=\gamma\log\beta\gamma-\gamma+\frac{1}{\beta}\leq\frac{\varepsilon}{4D}.$

Note that $\frac{\partial f}{\partial\beta}=\gamma/\beta-1/\beta^{2}>0$ and
$\frac{\partial f}{\partial\gamma}=\log\beta\gamma>0$ as long as
$\beta\gamma>1$. Since $f(1,1)=0$, we can find $\beta,\gamma>1$, close enough
to 1, such that $f(\beta,\gamma)\leq\varepsilon/(4D)$. We use these values of
$\beta$ and $\gamma$ (or, equivalently, $\tau$). Since
$k\ll(\beta/\alpha)^{k}$, there exists $\alpha\in(1,\beta)$, such that $(ii)$
holds. Summing $(i)$ and $(ii)$ shows that, for $n$ large enough,

$\log{\mathbb{P}}\biggl{(}\mathrm{Bin}(\tilde{m},p)=\bigl{\lceil}(\alpha/\beta)^{k}\gamma
mp\bigr{\rceil}\biggr{)}\geq-\frac{\varepsilon
mp}{2D}(1+o(1))\geq-\frac{\varepsilon\log n}{2}(1+o(1))\geq-\varepsilon\log
n.$

We proved that for $mp\lesssim\log n$, for any $\varepsilon>0$, for $n$ large
enough, there exists $\tau,\alpha,\beta$, such that

$\mathrm{Pr}\biggl{(}\mathrm{Bin}(\left\lfloor\beta^{-k-1}m\right\rfloor,p)=\lceil(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}\rceil\biggr{)}\geq
n^{-\varepsilon}.$

Since
$\beta^{-k-1}mp<\beta^{-k}mp<\lceil(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}\rceil$,
from binomial monotonicity, Lemma 13, we have that for any $\tilde{m}$ such
that $\beta^{-k-1}m\leq\tilde{m}\leq\beta^{-k}m$,

${\mathbb{P}}\Bigl{(}\mathrm{Bin}(\tilde{m},p)=\lceil(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}\rceil\Bigr{)}\geq
n^{-\varepsilon}.$

∎

###### Proof of Lemma 5.

We follow the argument in Lemma 14 with $k=0$ and $\mathbb{E}d_{\mathtt{max}}$
replaced by $\log n/(\log\log n-\log mp)$. Note that in the proof of Lemma 14,
in the case $mp\ll\log n$, we only used that
$mp\ll\mathbb{E}d_{\mathtt{max}}\ll\log n$ and $\mathbb{E}d_{\mathtt{max}}\leq
C\log n/(\log\log n-\log mp)$ for some $C>0$. Since both these properties
remain true upon replacing $\mathbb{E}d_{\mathtt{max}}$ with $\log n/(\log\log
n-\log mp)$, the proof follows. Since $\tau=\varepsilon/(8C)$, in the setting
of Lemma 5, and $C=1$ in this argument, we pick $\tau=\varepsilon/8$. ∎

## Appendix C. Proof of lemma 8

We proceed in the proof by first showing that there exists $\tilde{K}$, such
that $m-F_{\tilde{K}}\lesssim\tilde{K}$, and then, by increasing $\tilde{K}$
by a multiplicative factor, we find $K$ such that $m-F_{K}\leq K$.

### Case $mp\lesssim\log n$

From Lemma 14, there exist constants $\tau>0$, $\alpha,\beta$ with
$1<\alpha<\beta$, such that, for any $\tilde{m}$, satisfying
$\beta^{-k-1}m\leq\tilde{m}\leq\beta^{-k}m$, for all $n$ large enough,

${\mathbb{P}}\biggl{(}\mathrm{Bin}(\tilde{m},p)=\bigl{\lceil}(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}\bigr{\rceil}\biggr{)}\geq
n^{-\varepsilon}.$

Recall that in this case
$f_{t}=\bigl{\lceil}(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}\bigr{\rceil}$,
where $k$ is such that $\beta^{-k-1}m\leq m-F_{t-1}\leq\beta^{-k}m$ and
$F_{t}=\sum_{s=1}^{t}f_{s}$. From Lemma 14 we have that
${\mathbb{P}}(\mathrm{Bin}(m-F_{t-1},p)=f_{t})\geq n^{-\varepsilon}$. Our goal
is to prove that there exists $s\lesssim\text{val}\textsubscript{{LP}}\sim
m/\mathbb{E}d_{\mathtt{max}}$, such that $m-F_{s}\lesssim s$.

######  Lemma 15.

Let
$t^{(k)}:=\frac{\beta-1}{\beta\tau}\frac{m}{\mathbb{E}d_{\mathtt{max}}}\alpha^{-k}$.

If $\displaystyle m-F_{t-1}\leq\beta^{-k}m$ then $\displaystyle
m-F_{t+t^{(k)}-1}\leq\beta^{-k-1}m.$

Informally, if after $t-1$ steps of BlockGreedy, at most $\beta^{-k}m$ subsets
are uncovered, then after $t+t^{(k)}-1$ steps, at most $\beta^{-k-1}m$ subsets
remain uncovered.

###### Proof.

Let $s\geq t$. As long as $m-F_{s-1}>\beta^{-k-1}m$, we will always have
$f_{s}=\bigl{\lceil}(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}\bigr{\rceil}$.
We proceed by contradiction. Assume that $m-F_{t+t^{(k)}-1}>\beta^{-k-1}m$.
This implies that for all $s\in[t-1,t+t^{(k)}-1]$, we have
$f_{s}=f:=\bigl{\lceil}(\alpha/\beta)^{k}\tau\mathbb{E}d_{\mathtt{max}}\bigr{\rceil}$.
Therefore,

$F_{t+t^{(k)}-1}-F_{t-1}=t^{(k)}f\geq\frac{m(\beta-1)}{\beta^{k+1}}=\beta^{-k}m-\beta^{-k-1}m,$

and

$\displaystyle m-F_{t+t^{(k)}-1}$
$\displaystyle=m-F_{t-1}-\left(F_{t+t^{(k)}-1}-F_{t-1}\right)$
$\displaystyle\leq\beta^{-k}m-(\beta^{-k}m-\beta^{-k-1}m)=\beta^{-k-1}m.$

Therefore, we must have $m-F_{t+t^{(k)}-1}\leq\beta^{-k-1}m$. ∎

Note that we always have $\beta^{-1}m\leq m-F_{0}=m$. If we consecutively
apply Lemma 15 starting with $k=0$, then, for
$v(k)\coloneqq\sum_{s=0}^{k}t^{(s)}$ we have $m-F_{v(k)-1}\leq\beta^{-k-1}m$.
Therefore, for $k:=\frac{\log\mathbb{E}d_{\mathtt{max}}}{\log{\beta}}$, we
have $m-F_{v(k)-1}\leq\frac{m}{\mathbb{E}d_{\mathtt{max}}}$. We can bound

$v(k)\leq\sum_{s=0}^{\infty}t^{(k)}=\frac{\beta-1}{\beta\tau(\alpha-1)}\frac{m}{\mathbb{E}d_{\mathtt{max}}}\sim\frac{m}{\mathbb{E}d_{\mathtt{max}}}.$

From Lemma 7 we have $d_{\mathtt{max}}\lesssim\mathbb{E}d_{\mathtt{max}}$ with
high probability. Together with Lemma 1 this implies
$\text{val}\textsubscript{{LP}}\geq\frac{m}{d_{\mathtt{max}}}\gtrsim\frac{m}{\mathbb{E}d_{\mathtt{max}}}$.
Now, if we pick $\tilde{K}\coloneqq
v(k)\lesssim\frac{m}{\mathbb{E}d_{\mathtt{max}}}$, we have that
$\text{val}\textsubscript{{Alg}}\lesssim\frac{m}{\mathbb{E}d_{\mathtt{max}}}$.
Since $\text{val}\textsubscript{{LP}}\leq\text{val}\textsubscript{{Alg}}$, we
have that $\tilde{K}\sim\text{val}\textsubscript{{LP}}$ and
$m-F_{\tilde{K}}\lesssim\tilde{K}$.

### Case $mp\gg\log n$

Here, we have that $\mathbb{E}d_{\mathtt{max}}=mp(1+o(1))$, therefore, picking
an element that hits an average number of subsets is approximately the same as
picking an element that hits close to maximum number of subsets. From the
properties of the mean and the median of the binomial distribution, it follows
that
${\mathbb{P}}(\mathrm{Bin}(\tilde{m},p)\geq\left\lceil\tilde{m}p\right\rceil)\geq
1/3$, for any $\tilde{m}$.

We begin with the case $\log mp\ll\log n$. This means that $mp$ cannot grow
polynomially in $n$, but e.g. $mp\sim\log^{2}n$ is possible. In this regime,
$\text{val}\textsubscript{{IP}}\sim\frac{1}{p}\log\left(\frac{mp}{\log
n}\right)$. Let $K_{1}=\left\lceil\frac{1}{p}\log\left(\frac{mp}{\log
n}\right)\right\rceil$ and $f_{1},\ldots,f_{K_{1}}$ be a sequence such that
$f_{s}=\left\lceil mp(1-p)^{s}\right\rceil$. Then, we have that
$m-F_{K_{1}}\leq m(1-p)^{K_{1}}\leq\frac{1}{p}\log n$. Therefore,
$(m-F_{K_{1}})p\sim\log n$, and we can continue with $\tilde{f}_{t}$ from the
previous section $mp\sim\log n$, with
$\tilde{F}_{t}\coloneqq\sum_{s=1}^{t}\tilde{f}_{t}$. For this sequence
$\tilde{f}_{1},\ldots,\tilde{f}_{K_{2}}$, we have have
$K_{2}\lesssim\frac{1}{p}$, and
$m-F_{K_{1}}-\tilde{F}_{K_{2}}\lesssim\frac{1}{p}\ll\frac{1}{p}\log\left(\frac{mp}{\log
n}\right)$. The required statement holds for combined sequences $f_{t}$ and
$\tilde{f}_{t}$ and $\tilde{K}\coloneqq K_{1}+K_{2}$.
Finally, we study the case $\log mp\gtrsim\log n$, which implies that
$\text{val}\textsubscript{{IP}}\sim\frac{1}{p}\log n$. This case is trivial,
as one can pick $\tilde{K}=\left\lceil\frac{1}{p}\log\left(\frac{mp}{\log
n}\right)\right\rceil\lesssim\text{val}\textsubscript{{IP}}$ and
$f_{1},\ldots,f_{\tilde{K}}$ a sequence such that $f_{s}=\left\lceil
mp(1-p)^{s}\right\rceil$. Then, we have that $m-F_{\tilde{K}}\leq
m(1-p)^{\tilde{K}}\leq\frac{1}{p}\log
n\lesssim\text{val}\textsubscript{{IP}}$.

### From $m-F_{\tilde{K}}\lesssim\tilde{K}$ to $m-F_{K}\leq K$

Finally, using that $f_{t}\geq 1$ by Lemma 2 unless $F_{t}=m$, there exists
some constant $C>0$, such that for $K\coloneqq C\tilde{K}$, $F_{K}\geq m-K$,
which finishes the proof.