#  Repeated randomized algorithm for the Multicovering Problem

Abbass Gorgi<EMAIL_ADDRESS>Mourad El Ouali<EMAIL_ADDRESS>Anand Srivastav<EMAIL_ADDRESS>Mohamed Hachimi
<EMAIL_ADDRESS>Engineering Science Laboratory, University Ibn Zohr,
Agadir, Morocco  Department of Computer Science, Christian Albrechts
University, Kiel, Germany

###### Abstract

Let $\mathcal{H}=(V,\mathcal{E})$ be a hypergraph with maximum edge size
$\ell$ and maximum degree $\Delta$. For given numbers
$b_{v}\in\mathbb{N}_{\geq 2}$, $v\in V$, a set multicover in $\mathcal{H}$ is
a set of edges $C\subseteq\mathcal{E}$ such that every vertex $v$ in $V$
belongs to at least $b_{v}$ edges in $C$. set multicover is the problem of
finding a minimum-cardinality set multicover. Peleg, Schechtman and Wool
conjectured that unless $\mathcal{P}=\mathcal{NP}$, for any fixed $\Delta$ and
$b:=\min_{v\in V}b_{v}$, no polynomial-time approximation algorithm for the
set multicover problem has an approximation ratio less than
$\delta:=\Delta-b+1$. Hence, it’s a challenge to know whether the problem of
set multicover is not approximable within a ratio of $\beta\delta$ with a
constant $\beta<1$.

This paper proposes a repeated randomized algorithm for the set multicover
problem combined with an initial deterministic threshold step. Boosting
success by repeated trials, our algorithm yields an approximation ratio of
$\max\left\\{\frac{15}{16}\delta,\left(1-\frac{(b-1)\exp\left(\frac{3\delta+1}{8}\right)}{72\ell}\right)\delta\right\\}$.
The crucial fact is not only that our result improves over the approximation
ratio presented by Srivastav et al (Algorithmica 2016) for any $\delta\geq
13$, but it’s more general since we set no restriction on the parameter
$\ell$.
Furthermore, we prove that it is NP-hard to approximate the set multicover
problem on $\Delta$-regular hypergraphs within a factor of
$(\delta-1-\epsilon)$.
Moreover we show that the integrality gap for the set multicover problem is at
least $\frac{\ln_{2}(n+1)}{2b}$, which for constant $b$ is $\Omega(\ln n)$.

###### keywords:

Integer linear programs, hypergraphs, approximation algorithms, randomized
rounding, set cover and set multicover.

##  1 Introduction

This work was intended as an attempt to solve approximately the set multicover
problem. A nice formulation of this problem may be given by the notion of
hypergraphs.

A hypergraph is a pair $\mathcal{H}=(V,\mathcal{E})$, where $V$ is a finite
set and $\mathcal{E}\subseteq 2^{V}$ is a family of some subsets of $V$. We
call the elements of $V$ vertices and the elements of $\mathcal{E}$
(hyper-)edges. Further, let $n:=|V|$, $m:=|{\cal E}|$. W.l.o.g. let the
vertices be enumerated as $v_{1},v_{2},\dots,v_{n}$ and the edges as
$E_{1},E_{2},\dots,E_{m}$. As usually the degree of a vertex $v$ (notation
$d(v)$) is the number of hyperedges it appears in. Let $\Delta:=\max_{v\in
V}d(v)$ be the maximum degree. Furthermore, if the degree of every vertex is
exactly $\Delta$, then ${\cal H}$ is called $\Delta$-regular. We define the
number of vertices of a hyperedge as its size. If the size of all hyperedges
is exactly $\ell$, i.e., $\forall E\in\mathcal{E},\,|E|=\ell$, then
$\mathcal{H}$ is $\ell$-uniform. Let
$\mathbf{b}:=(b_{1},b_{2},\dots,b_{n})\in\mathbb{N}_{\geq 2}^{n}$ be given. If
a vertex $v_{i}$, $i\in[n]$, is contained in at least $b_{i}$ edges of some
subset $C\subseteq\mathcal{E}$, we say that the vertex $v_{i}$ is fully
covered by $b_{i}$ edges in $C$. A set multicover in $\mathcal{H}$ is a set of
edges $C\subseteq\mathcal{E}$ such that every vertex $v_{i}$ in $V$ is fully
covered by $b_{i}$ edges in $C$. The set multicover problem is the task of
finding a set multicover of minimum cardinality.

Related Work. The set cover problem $(b=1)$ is known to be NP-hard [14] and
has been intensively explored for decades. Several deterministic approximation
algorithms are exhibited for this problem [1, 10, 12, 16], all with
approximation ratios $\Delta$. Furthermore, Johnson [13] and Lovász [17] gave
a greedy algorithm with performance ratio $H(\ell)$, where
$H(\ell)=\sum_{i=1}^{\ell}\frac{1}{i}$ is the harmonic number. Notice that
$H(\ell)\leq 1+\ln(\ell)$. For hypergraphs with bounded $\ell$, Duh and Fürer
[4] used the technique called semi-local optimization, improving $H(\ell)$ to
$H(\ell)-\frac{1}{2}$.
Unlike the set cover problem, the case $b\geq 2$ of the set multicover problem
is less known. Let us give a summary of the known approximability results. In
paper [21], Vazirani using primal-dual schema extended the result of Lovász
[17] for $b\geq 1$. Later Fujito et al. [9] improved the algorithm of Vazirani
and achieved an approximation ratio of $H(\ell)-\frac{1}{6}$ for $\ell$
bounded. Hall and Hochbaum [11] achieved by a greedy algorithm based on LP
duality an approximation ratio of $\Delta$. By a deterministic threshold
algorithm Peleg, Schechtman, and Wool in 1997 [19, 20] improved this result
and gave an approximation ratio of $\delta$. They were also the first to
propose an approximation algorithm for the set multicover problem with
approximation ratio below $\delta$, namely a randomized rounding algorithm
with performance ratio $(1-(\frac{c}{n})^{\frac{1}{\delta}})\cdot\delta$ for a
small constant $c>0$. However, their ratio is depending on $n$, and
asymptotically tends to $\delta$. Furthermore Peleg, Schechtman and Wool
conjectured that for any fixed $\Delta$ and $b:=\min_{i\in[n]}b_{i}$ the
problem cannot be approximated by a ratio smaller than $\delta:=\Delta-b+1$
unless $\mathcal{P}=\mathcal{NP}$. Hence it remained an open problem whether
an approximation ratio of $\beta\delta$ with $\beta<1$ constant can be proved.
A randomized algorithm of hybrid type was later given by Srivastav et al [7].
Their algorithm achieves for hypergraphs with
$l\in\mathcal{O}\left(\max\\{(nb)^{\frac{1}{5}},n^{\frac{1}{4}}\\}\right)$ an
approximation ratio of $\left(1-\frac{11(\Delta-b)}{72l}\right)\cdot\delta$
with constant probability.
Concerning the algorithmic complexity, the set multicover problem has still
not been investigated. In contrast to the set cover problem, it is known that
the problem is hard to approximate to within $\Delta-1-\epsilon$, unless
$\mathcal{P}=\mathcal{NP}$ [2], and to within $\Delta-\epsilon$ under the UGC
[15] for any fixed $\epsilon>0$. Unless $\mathcal{P}=\mathcal{NP}$ there is no
$(1-\epsilon)\ln n$ approximation [8]. This motivated us to study this aspect
of the problem.
Our Results. The main contribution of our paper is the combination of a
deterministic threshold-based algorithm with repeated randomized rounding
steps. The idea is to algorithmically discard instances that can be handled
deterministically in favor of instances for which we obtain a constant-factor
approximation less than $\delta$ using a repeated randomized strategy.

Our hybrid randomized algorithm is designed as a cascade of a deterministic
and a repeated randomized rounding step followed by greedy repair if the
randomized solution is not feasible. First, the relaxed problem of the set
multicover problem is solved. The successive actions depend on the cardinality
of a set of hyperedges that will be defined according to the relaxed problem
output. Our algorithm is an extension of an example given in [5, 6, 7, 10, 11,
20] for the vertex cover, partial vertex cover and set multicover problem in
graphs and hypergraphs.

The methods used in this paper rely on an application of an extension of the
Chernoff-Hoeffding bound theorem for sums of independent random variables and
are based on estimating the variance of the summed random variables for
invoking the Chebychev-Cantelli inequality. Our algorithm yields a performance
ratio of
$\max\left\\{\frac{15}{16}\delta,\left(1-\frac{(b-1)\exp\left(\frac{3\delta+1}{8}\right)}{72\ell}\right)\delta\right\\}$.
This ratio means a constant factor of less than $\delta$ for many settings of
the parameters $\delta$, $b$, and $\ell$. It is asymptotically better than the
former approximation ratios due to Peleg et al. and Srivastav et al.
Furthermore, using a reduction of the set cover problem on $\Delta$-regular
hypergraphs to the set multicover problem on $\Delta+b-1$-regular hypergraphs,
we show that it is NP-hard to approximate the set multicover problem on
$\Delta$-regular hypergraphs within a factor of $(\delta-1-\epsilon)$.
Moreover, we show that the integrality gap for the natural LP formulation of
the set multicover problem is at least $\frac{\ln_{2}(n+1)}{2b}$, which for
constant $b$ is $\Omega(\ln n)$.

Fundamental results and approximations for set multicover problem

Hypergraph | Approximation ratio
---|---
- |  $H(\ell)$[21]
bounded $\ell$ |  $H(\ell)-\frac{1}{6}$ [9]
- |  $\delta$ [11, 20]
- |  $(1-(\frac{c}{n})^{\frac{1}{\delta}})\cdot\delta$ where $c>0$ is a constant. [19]
$l\in\mathcal{O}\left(\max\\{(nb)^{\frac{1}{5}},n^{\frac{1}{4}}\\}\right)$ |  $\left(1-\frac{11(\Delta-b)}{72\ell}\right)\cdot\delta$ [7]
- |  $\max\left\\{\frac{15}{16}\delta,\left(1-\frac{(b-1)\exp\left(\frac{3\delta+1}{8}\right)}{72\ell}\right)\delta\right\\}$ (this paper)

Outline of the paper. In Section 2, we give all the definitions and the tools
needed for our analysis. In Section 3, we present a randomized algorithm of
hybrid type and its analysis. In Section 4, we give a lower bound for the
problem. In Section 5, we discuss the integrality gap of the LP formulation of
the problem.

##  2  Definitions and preliminaries

For the later analysis we will use the following extension of Chernoff-
Hoeffding Bound inequality for a sum of independent random variables. It is
often used if one only has a bound on the expectation:

######  Theorem 1 (see [3])

Let $X_{1},\ldots,X_{n}$ be independent $\\{0,1\\}$-random variables. Let
$X=\sum_{i=1}^{n}X_{i}$ and suppose $\mathbb{E}(X)<\mu$. For every
$0<\beta\leq 1$ we have

$\Pr[X\geq(1+\beta)\mu]\leq\exp{\left(-\frac{\beta^{2}\mu}{3}\right)}.$

A further useful concentration theorem we will use is the Chebychev-Cantelli
inequality:

######  Theorem 2 (see [18], page 64)

Let $X$ be a non-negative random variable with finite mean $\mathbb{E}(X)$ and
variance Var$(X)$. Then for any $a>0$ it holds that

$\displaystyle\Pr(X\leq\mathbb{E}(X)-a)$ $\displaystyle\leq$
$\displaystyle\frac{{\rm Var}(X)}{{\rm Var}(X)+a^{2}}\cdot$

Our lower bound proof for the problem relies on extending the following
theorem from the case of $b=1$ to the case of $b\geq 2$.

######  Theorem 3 (I. Dinur et al, 2005 [2])

For every integer $l\geq 3$ and every $\epsilon>0$, it is NP-hard to
approximate the minimum vertex cover problem on $\ell$-uniform hypergraphs
within a factor of $(\ell-1-\epsilon)$.

A key notion of linear programming relaxations is the concept of Integrality
Gap.

###### Definition 1

Let $\cal{I}$ be a set of instances, the Integrality Gap for minimization
problems is defined as

$\sup_{i\in\cal{I}}{\frac{{\rm Opt}(I)}{{\rm Opt}^{*}(I)}}.$

##  3  The multi-randomized rounding algorithm

Let ${\cal H}=(V,{\cal E})$ be a hypergraph with maximum vertex degree
$\Delta$ and maximum edge size $\ell$. An integer linear programming
formulation of the set multicover problem is the following:

$\displaystyle\min\sum_{j=1}^{m}x_{j},$ $\displaystyle\mbox{ILP}(\Delta,{\bf
b}):\qquad$ $\displaystyle\sum_{j=1}^{m}a_{ij}x_{j}\geq b_{i}\quad\mbox{ for
all }i\in[n],$ $\displaystyle x_{j}\in\\{0,1\\}\quad\mbox{ for all }j\in[m],$

where $A=(a_{ij})_{i\in[n],\,j\in[m]}\in\\{0,1\\}^{n\times m}$ is the vertex-
edge incidence matrix of ${\cal H}$ and ${\bf
b}=(b_{1},b_{2},\dots,b_{n})\in\mathbb{N}_{\geq 2}^{n}$ is the given integer
vector. For every vertex $v$, we define
$\Gamma(v):=\\{E\in\mathcal{E}\mathrel{|}v\in E\\}$ the set of edges incident
to $v$.
The linear programming relaxation LP($\Delta,\,{\bf b}$) of ILP($\Delta,\,{\bf
b}$) is given by relaxing the integrality constraints to $x_{j}\in[0,1]$ for
all $j\in[m]$. Let $\mathrm{Opt}$ resp. ${\rm Opt}^{*}$ be the value of an
optimal solution to ILP($\Delta,\,{\bf b}$) resp. LP($\Delta,\,{\bf b}$). Let
$(x^{\ast}_{1},\ldots,x^{\ast}_{m})$ be the optimal solution of the
LP($\Delta,\,{\bf b}$). So ${\rm Opt}^{*}=\sum_{j=1}^{m}x^{*}_{j}$ and ${\rm
Opt}^{*}\leq\mathrm{Opt}$.

The next lemma shows that the $b_{i}$ greatest values of the LP variables
corresponding to the incident edges for any vertex $v_{i}$ are all greater
than or equal to $\frac{1}{\delta}$.

######  Lemma 1 (see [20])

Let $b_{i},d,\Delta,n\in\mathbb{N}$ with $2\leqslant b_{i}\leqslant
d-1\leqslant\Delta-1,i\in[n]$ . Let $x_{j}\in[0,1],j\in[d]$, such that
$\displaystyle\sum_{j=1}^{d}x_{j}\geqslant b_{i}$. Then at least $b_{i}$ of
the $x_{j}$ fulfill the inequality $x_{j}\geqslant\frac{1}{\delta}$.

Our second lemma shows that the $b_{i}-1$ greatest values of the LP variables
corresponding to the incident edges for any vertex $v_{i}$ are all greater
than or equal to $\frac{2}{\delta+1}$ and with Lemma 1 we take the sum over
the $b_{i}$ greatest values of the LP variables corresponding to the incident
edges for any vertex $v_{i}$.

###### Lemma 2

Let $b_{i},d,\Delta,n\in\mathbb{N}$ with $2\leqslant b_{i}\leqslant
d-1\leqslant\Delta-1,i\in[n]$ . Let $x_{j}\in[0,1],j\in[d]$, such that
$\displaystyle\sum_{j=1}^{d}x_{j}\geqslant b_{i}$. Then at least $b_{i}-1$ of
the $x_{j}$ fulfill the inequality $x_{j}\geqslant\frac{2}{\delta+1}$ and
there exists an element $x_{j}$, distinct to all of them, that fulfills the
inequality $x_{j}\geqslant\frac{1}{\delta}$ .

###### Proof 1

W.l.o.g. we suppose $x_{1}\geq x_{2}\geq\cdots\geq x_{b_{i}}\geq\cdots\geq
x_{d}$.
Hence $b_{i}-2\geq\displaystyle\sum_{j=1}^{b_{i}-2}x_{j}$ and
$(d-b_{i}+2)x_{b_{i-1}}\geq\displaystyle\sum_{j=b_{i}-1}^{d}x_{j}$.
Then

$\displaystyle b_{i}-2+(\Delta-b+2)x_{b_{i}-1}$ $\displaystyle\geq$
$\displaystyle b_{i}-2+(\Delta-b_{i}+2)x_{b_{i}-1}$ $\displaystyle\geq$
$\displaystyle b_{i}-2+(d-b_{i}+2)x_{b_{i}-1}$ $\displaystyle\geq$
$\displaystyle\sum_{j=1}^{b_{i}-2}x_{j}+\sum_{j=b_{i}-1}^{d}x_{j}=\displaystyle\sum_{j=1}^{d}x_{j}$
$\displaystyle\geq$ $\displaystyle b_{i}$

So we have $x_{b_{i}-1}\geq\frac{2}{\delta+1}$.
Since for all $j\in[b_{i}-1]\;,\ x_{j}\geq x_{b_{i}-1}$ then for all
$j\in[b_{i}-1]\;,\;x_{j}\geq\frac{2}{\delta+1}$.
Furthermore, by Lemma $1$ and the assumption on the orders of the variables
$x_{j}$, for all $j\in[b_{i}]\;$ we have $x_{j}\geq\frac{1}{\delta}$ and
particularly $x_{b_{i}}\geq\frac{1}{\delta}$.

###  3.1 The algorithm

In this section we present an algorithm with conditioned randomized rounding
based on the properties satisfied by two generated sets, $C_{1}$ and $C_{2}$.

Input : A hypergraph $\mathcal{H}=(V,\,\mathcal{E})$ with maximum degree
$\Delta$ and maximum hyperedge size $\ell$, numbers $b_{i}\in\mathbb{N}_{\geq
2}\text{ for }i\in[n]$, $b:=\min_{i\in[n]}b_{i}$, $\epsilon\in(0,1)$, a
constant $k\in\mathbb{N}_{\geq 2}$ and $\delta=\Delta-b+1$.

Output : A set multicover $C$

  1. 1.

Initialize $C:=\emptyset$. Set $\lambda=\frac{\delta+1}{2}\;$,
$\alpha=\frac{(b-1)\delta\epsilon^{k}}{6\ell}\times\exp\left(a_{k,\epsilon}\right)$
with $a_{k,\epsilon}=\frac{k(1-\epsilon)+(\delta-1)(1-\epsilon^{a})}{2}$ and
$\lambda_{0}=(1-\epsilon)\delta$.

  2. 2.

Obtain an optimal solution $x^{*}\in[0,1]^{m}$ by solving the
LP($\Delta,\,{\bf b}$) relaxation.

  3. 13.

Set
$C_{1}:=\\{E_{j}\in\mathcal{E}\mathrel{|}x_{j}^{\ast}\geq\frac{1}{\lambda}\\}$,
$\
C_{2}:=\\{E_{j}\in\mathcal{E}\mathrel{|}\frac{1}{\lambda}>x_{j}^{\ast}\geq\frac{1}{\delta}\\}$

and
$C_{3}:=\\{E_{j}\in\mathcal{E}\mathrel{|}0<x_{j}^{\ast}<\frac{1}{\delta}\\}$.

* 4.

Take all edges of the set $C_{1}$ in the cover $C$. 25. if
$|C_{1}|\geq\alpha\cdot\mathrm{Opt}^{*}$ then return $C=C_{1}\cup C_{2}$.

Else (Multi-randomized Rounding)

  1. 3(a)

For all edges $E_{j}\in C_{2}$ include the edge $E_{j}$ in the cover $C$,
independently for all such $E_{j}$, with probability $\lambda_{0}x_{j}^{*}$,
$k$ times.

4 $\left(\text{ If, in any of these $k$ biased coin flips shows head, include
the edge }E_{j}\text{ in the cover.}\right)$

* (b)

For all edges $E_{j}\in C_{3}$ include the edge $E_{j}$ in the cover $C$,
independently for all such $E_{j}$, with probability $(1-\epsilon^{k})\delta
x_{j}^{*}$. (c) (Repairing) Repair the cover $C$ (if necessary) as follows:
Include arbitrary edges from $C_{2}$, incident to the vertices $v_{i}$ not
fully covered, to $C$ until all vertices are fully covered. (d) Return the
cover $C$.

Algorithm 1 SET MULTICOVER

In step $2$ we solve the linear programming relaxation LP($\Delta,\,{\bf b}$)
in polynomial time, using some known polynomial-time procedure, e.g. the
interior point method. Next we take into the cover all edges of the sets
$C_{1}$ resp. $C_{2}$. Since the LP variable value $x^{*}_{j}$ that
corresponds to an edge $E_{j}$ from the set $C_{1}$ is greater than or equal
to $\frac{2}{\delta+1}$ and the value $x^{*}_{j}$ that corresponds to an edge
$E_{j}$ from the set $C_{2}$ is less than $\frac{2}{\delta+1}$, we have

$|C_{1}|+|C_{2}|=|C|\text{\quad and\quad}C_{1}\cap C_{2}=\emptyset$ (1)

###  3.2 Analysis of the algorithm

Case $\mathbf{|C_{1}|\geq\alpha\cdot\mathrm{Opt}^{*}}$.

###### Theorem 4

Let $\mathcal{H}$ be a hypergraph with maximum vertex degree $\Delta$ and
maximum edge size $\ell$. Let
$\alpha=\frac{(b-1)\delta\epsilon^{k}}{6\ell}\times\exp\left(a_{k,\epsilon}\right)$
with $a_{k,\epsilon}=\frac{k(1-\epsilon)+(\delta-1)(1-\epsilon^{a})}{2}$ as
defined in Algorithm 1. If $|C_{1}|\geq\alpha\cdot\mathrm{Opt}^{*}$ then
Algorithm 1 returns a set multicover $C$ such that

$|C|<\left(1-\frac{(b-1)\epsilon^{k}}{18\ell}\times\exp\left(a_{k,\epsilon}\right)\right)\delta\cdot\mathrm{Opt}^{*}$

###### Proof 2

The proof is straightforward, using the definitions of the sets $C_{1}$ and
$C_{2}$.

$\displaystyle\delta\mathrm{Opt}^{*}=\sum_{j=1}^{m}\delta x^{*}_{j}$
$\displaystyle\geq$ $\displaystyle\displaystyle\sum_{E_{j}\in C_{1}}\delta
x^{*}_{j}+\sum_{E_{j}\in C_{2}}\delta x^{*}_{j}$ $\displaystyle\geq$
$\displaystyle\frac{2\delta}{\delta+1}|C_{1}|+|C_{2}|$ $\displaystyle\geq$
$\displaystyle\frac{2\delta}{\delta+1}|C_{1}|+\left(|C|-|C_{1}|\right)$
$\displaystyle\geq$ $\displaystyle\frac{\delta-1}{\delta+1}|C_{1}|+|C|$
$\displaystyle\overset{\delta\geq 2}{\geq}$
$\displaystyle\frac{1}{3}|C_{1}|+|C|$ $\displaystyle\geq$
$\displaystyle\frac{1}{3}\alpha\cdot\mathrm{Opt}^{*}+|C|.$

Hence

$|C|\leq\left(1-\frac{(b-1)\epsilon^{k}}{18\ell}\times\exp\left(a_{k,\epsilon}\right)\right)\delta\cdot\mathrm{Opt}^{*}$

Case $\mathbf{|C_{1}|<\alpha\cdot\mathrm{Opt}^{*}}$.

Let $X_{1},\ldots,X_{m}$ be $\\{0,1\\}$-random variables defined as follows:

$\displaystyle X_{j}=\begin{cases}1&\text{if the edge}\,E_{j}\,\text{was
picked into the cover before repairing}\\\ 0&\text{otherwise}.\end{cases}$

Note that the $X_{1},\ldots,X_{m}$ are independent for a given
$x^{*}\in[0,1]^{m}$. For all $i\in[n]$ we define the $\\{0,1\\}$\- random
variables $Y_{i}$ as follows:

$\displaystyle Y_{i}=\begin{cases}1&\text{if the vertex}~{}v_{i}~{}\text{is
fully covered before repairing}\\\ 0&\text{otherwise}.\end{cases}$

We denote by $X:=\sum_{j=1}^{m}X_{j}$ and $Y:=\sum_{i=1}^{n}Y_{i}$ the
cardinality of the cover and the cardinality of the set of fully covered
vertices before the step of repairing, respectively. At this step by Lemma 2,
one more edge for each vertex is at most needed to be fully covered. The cover
$C$ obtained by Algorithm 1 is bounded by

$\left\lvert C\right\rvert\leq X+n-Y.$ (2)

Our next lemma provides upper bounds on the expectation of the random variable
$X$ and the expectation and variance of the random variable $Y$, which we will
use to proof Theorem 5. This is a restriction of Lemma $4$ in [7] to the last
case in Algorithm 1.

###### Lemma 3

Let $l$ and $\Delta$ be the maximum size of an edge and the maximum vertex
degree, respectively. Let
$\epsilon\in\left[\frac{\delta-1}{2\delta},\left(\frac{\delta-1}{2\delta}\right)^{\frac{1}{k}}\right]$,
$a_{k,\epsilon}=\frac{k(1-\epsilon)+(\delta-1)(1-\epsilon^{a})}{2}$,
$\lambda_{0}=(1-\epsilon)\delta$ and $\lambda=\frac{\delta+1}{2}$ as in
Algorithm 1. We have

$\mathrm{(i)}$ $\mathbb{E}(Y)\geq(1-\exp\left(-2a_{k,\epsilon}\right))n$.

$\mathrm{(ii)}$ ${\rm Var}(Y)\leq 2n^{2}\exp\left(-2a_{k,\epsilon}\right)$.

$\mathrm{(iii)}$ $\mathbb{E}(X)\leq(1-\epsilon^{k})\delta\mathrm{Opt}^{*}$.

$\mathrm{(iv)}$ $\dfrac{(b-1)n}{\alpha\ell}<\mathrm{Opt}^{*}$.

###### Proof 3

(i) Let $i\in[n]$, $r=d(i)-b_{i}+1$. If $\left\lvert
C_{1}\cap\Gamma(v_{i})\right\rvert\geq b_{i}$, then the vertex $v_{i}$ is
fully covered and $\Pr(Y_{i}=0)=0$. Otherwise we get by Lemma 2 that
$\left\lvert C_{1}\cap\Gamma(v_{i})\right\rvert=b_{i}-1$ and there exists at
least one more edge from $C_{2}$ with $x_{j}\geq\frac{1}{\delta}$, so we have
$\sum_{E_{j}\in\Gamma(v_{i})\cap C_{2}}x_{j}^{*}\geq\frac{1}{\delta}$ and by
the inequality constraints it holds that
$\sum_{E_{j}\in\Gamma(v_{i})\cap\left(C_{2}\cup C_{3}\right)}x_{j}^{*}\geq 1$.
Therefore

$\displaystyle\Pr(Y_{i}=0)$ $\displaystyle=$
$\displaystyle\left(\prod_{E_{j}\in\Gamma(v_{i})\cap
C_{2}}(1-\lambda_{0}x_{j}^{*})\right)^{k}\prod_{E_{j}\in\Gamma(v_{i})\cap
C_{3}}\left(1-(1-\epsilon^{k})\delta x_{j}^{*}\right)$ $\displaystyle=$
$\displaystyle\prod_{E_{j}\in\Gamma(v_{i})\cap
C_{2}}\left(1-\lambda_{0}x_{j}^{*}\right)^{k}\prod_{E_{j}\in\Gamma(v_{i})\cap
C_{3}}\left(1-(1-\epsilon^{k})\delta x_{j}^{*}\right)$ $\displaystyle\leq$
$\displaystyle\prod_{E_{j}\in\Gamma(v_{i})\cap
C_{2}}\exp(-k\lambda_{0}x_{j}^{*})\prod_{E_{j}\in\Gamma(v_{i})\cap
C_{3}}\exp(-(1-\epsilon^{k})\delta x_{j}^{*})$ $\displaystyle=$
$\displaystyle\exp\left(-k(1-\epsilon)\delta\sum_{E_{j}\in\Gamma(v_{i})\cap
C_{2}}x_{j}^{*}\right)\cdot\exp\left(-(1-\epsilon^{k})\delta\sum_{E_{j}\in\Gamma(v_{i})\cap
C_{3}}x_{j}^{*}\right)$ $\displaystyle=$
$\displaystyle\exp\left(\left(-k(1-\epsilon)+(1-\epsilon^{k})\right)\delta\sum_{E_{j}\in\Gamma(v_{i})\cap
C_{2}}x_{j}^{*}\right)\cdot\exp\left(-(1-\epsilon^{k})\delta\sum_{E_{j}\in\Gamma(v_{i})\cap\left(C_{2}\cup
C_{3}\right)}x_{j}^{*}\right).$

Since $1-\epsilon^{k}=(1-\epsilon)\sum_{i=0}^{k-1}\epsilon^{i}\leq
k(1-\epsilon)$, we have $-k(1-\epsilon)+1-\epsilon^{k}\leq 0$.

It follows that

$\displaystyle\Pr(Y_{i}=0)$ $\displaystyle\leq$
$\displaystyle\exp\left(-k(1-\epsilon)+(1-\epsilon^{k})\right)\cdot\exp\left(-(1-\epsilon^{k})\delta\right)$
$\displaystyle=$ $\displaystyle\exp\left(-2a_{k,\epsilon}\right).$

Therefore

$\displaystyle\mathbb{E}(Y)$
$\displaystyle=\sum_{i=1}^{n}\Pr(Y_{i}=1)=\sum_{i=1}^{n}(1-\Pr(Y_{i}=0))$
$\displaystyle\geq\sum_{i=1}^{n}(1-\exp\left(-2a_{k,\epsilon}\right))$
$\displaystyle\geq(1-\exp\left(-2a_{k,\epsilon}\right))n.$

(ii) Since

$Y=\sum_{i=1}^{n}Y_{i}\leq n,$

we have

$\mathbb{E}(Y^{2})\leq n^{2}.$

Thus,

$\displaystyle{\rm Var}(Y)$
$\displaystyle=\mathbb{E}(Y^{2})-\mathbb{E}(Y)^{2}\leq
n^{2}-(1-\exp\left(-2a_{k,\epsilon}\right))^{2}n^{2}$ $\displaystyle\leq
n^{2}\left(1-(1-\exp\left(-2a_{k,\epsilon}\right))^{2}\right)$
$\displaystyle\leq 2n^{2}\exp\left(-2a_{k,\epsilon}\right).$

(iii) Let $E_{j}$ be an edge from $C_{2}$. By Lemma 2 we have
$\frac{1}{\delta}\leq x^{*}_{j}<\frac{2}{\delta+1}$.
Recall that we include independently the edge $E_{j}$ in the cover $C$, with
probability $\lambda_{0}x_{j}^{*}$, $k$ times. Since
$\frac{\delta-1}{2\delta}\leq\epsilon$, we have
$1-\epsilon\leq\lambda_{0}x^{*}_{j}<\frac{2}{\delta+1}(1-\epsilon)\delta\leq\frac{2}{\delta+1}(1-\frac{\delta-1}{2\delta})\delta=1$.
Furthermore with
$\epsilon\leq\left(\frac{\delta-1}{2\delta}\right)^{\frac{1}{k}}$ we have
$\left(1-\epsilon^{k}\right)\delta\geq\left(1-\frac{\delta-1}{2\delta}\right)\delta=\frac{\delta+1}{2}=\lambda$.
Then

$\lambda\leq\left(1-\epsilon^{k}\right)\delta.$ (3)

Clearly $\Pr\left(X_{j}=1\right)=1-\left(1-\lambda_{0}x^{*}_{j}\right)^{k}$.

Define the function $f$ by $f(x)=\frac{1-(1-x)^{k}}{x}$.
$f$ is strictly decreasing on $(0,1]$. Therefore,
$\
\frac{1-\left(1-\lambda_{0}x^{*}_{j}\right)^{k}}{\lambda_{0}x^{*}_{j}}\leq\frac{1-\left(1-(1-\epsilon)\right)^{k}}{1-\epsilon}=\frac{1-\epsilon^{k}}{1-\epsilon}$.

It follows that
$\Pr\left(X_{j}=1\right)\leq\frac{1-\epsilon^{k}}{1-\epsilon}\cdot\lambda_{0}x^{*}_{j}$.

Then

$\Pr\left(X_{j}=1\right)\leq\left(1-\epsilon^{k}\right)\delta x^{*}_{j}.$ (4)

By using the LP relaxation and the definition of the sets $C_{1}$ and $C_{2}$,
and since $\lambda x^{*}_{j}\geq 1$ for all ${E_{j}\in C_{1}}$, we get

$\displaystyle\mathbb{E}(X)$ $\displaystyle=$
$\displaystyle|C_{1}|+\sum_{E_{j}\in
C_{2}}\Pr\left(X_{j}=1\right)+\sum_{E_{j}\in C_{3}}\Pr\left(X_{j}=1\right)$
$\displaystyle\overset{(\ref{probability5})}{\leq}$
$\displaystyle\sum_{E_{j}\in C_{1}}\lambda x^{*}_{j}+\sum_{E_{j}\in
C_{2}}(1-\epsilon^{k})\delta x^{*}_{j}+\sum_{E_{j}\in
C_{3}}(1-\epsilon^{k})\delta x^{*}_{j}$
$\displaystyle\overset{(\ref{probability4})}{\leq}$
$\displaystyle(1-\epsilon^{k})\delta\sum_{E_{j}\in\mathcal{E}}x^{*}_{j}$
$\displaystyle\leq$ $\displaystyle(1-\epsilon^{k})\delta\mathrm{Opt}^{*}.$

(iv) Let us consider $\tilde{\mathcal{H}}$ the subhypergraph induced by
$C_{1}$ in which degree equality gives

$\sum_{i\in V}d(i)=\sum_{E_{j}\in C_{1}}|E_{j}|.$

As the minimum vertex degree in the subhypergraph $\tilde{\mathcal{H}}$ is
$b-1$ with $b:=\min_{i\in[n]}b_{i}$, we have

$(b-1)n\leq\sum_{i\in V}d(i)=\sum_{E\in C_{1}}|E_{j}|\leq\ell|C_{1}|.$

Therefore

$\frac{(b-1)n}{\ell}\leq|C_{1}|.$

Since $|C_{1}|<\alpha\cdot\mathrm{Opt}^{*}$ we obtain

$\displaystyle\frac{(b-1)n}{\alpha\ell}<\mathrm{Opt}^{*}.$

###### Theorem 5

Let $\mathcal{H}$ be a hypergraph with fixed maximum vertex degree $\Delta$
and maximum edge size $\ell$. Let
$\alpha=\frac{(b-1)\delta\epsilon^{k}}{6\ell}\times\exp\left(a_{k,\epsilon}\right)$
with $a_{k,\epsilon}=\frac{k(1-\epsilon)+(\delta-1)(1-\epsilon^{k})}{2}$ and
$\epsilon\in\left[\frac{\delta-1}{2\delta},\left(\frac{\delta-1}{2\delta}\right)^{\frac{1}{k}}\right]$
as in Algorithm 1. The Algorithm 1 returns a set multicover $C$ such that

$|C|<\max\left\\{\left(1-\frac{1}{2}\left(1-\epsilon\right)\epsilon^{k}\right)\delta,\left(1-\frac{(b-1)\epsilon^{k}}{18\ell}\times\exp\left(a_{k,\epsilon}\right)\right)\delta\right\\}\cdot\mathrm{Opt}^{*}$

with probability greater than $0.65$.

###### Proof 4

Let $\mathcal{C}$ be the event that the inequality
$|C|<\left(1-\frac{1}{2}\left(1-\epsilon\right)\epsilon^{k}\right)\delta\cdot\mathrm{Opt}^{*}$
is satisfied. It suffices to prove that event $\mathcal{C}$ holds with the
given probability in the case $|C_{1}|<\alpha\cdot\mathrm{Opt}^{*}$ since the
opposite case is discussed in Theorem 4. For this purpose, we estimate both
the concentration of $X$ and $Y$ around their expectation. Choose
$t=2n\exp\left(-a_{k,\epsilon}\right)$ and consider $\mathcal{A}$ the event
$Y\leq n(1-\exp\left(-2a_{k,\epsilon}\right))-t$.
This involves

$\displaystyle n\exp\left(-2a_{k,\epsilon}\right)+t$ $\displaystyle=$
$\displaystyle
n\exp\left(-2a_{k,\epsilon}\right)+2n\exp\left(-a_{k,\epsilon}\right)$
$\displaystyle\leq$ $\displaystyle 3n\exp\left(-a_{k,\epsilon}\right)$
$\displaystyle=$
$\displaystyle\frac{n(b-1)}{\ell}\cdot\frac{6\ell}{(b-1)\delta\epsilon^{k}\exp\left(a_{k,\epsilon}\right)}\cdot\frac{1}{2}\epsilon^{k}\delta$
$\displaystyle=$
$\displaystyle\frac{n(b-1)}{\alpha\ell}\cdot\frac{1}{2}\epsilon^{k}\delta$
$\displaystyle\overset{\textrm{Lem }~{}\ref{lemma:random}(iv)}{\leq}$
$\displaystyle\frac{1}{2}\epsilon^{k}\delta\cdot\mathrm{Opt}^{*}.$

And by Lemma 3(ii) we have $\frac{t^{2}}{{\rm
Var}(Y)}\geq\frac{4n^{2}\exp\left(-2a_{k,\epsilon}\right)}{2n^{2}\exp\left(-2a_{k,\epsilon}\right)}=2$.

Therefore

$\displaystyle\Pr\left(\mathcal{A}\right)$ $\displaystyle\leq$
$\displaystyle\Pr\left(Y\leq\mathbb{E}(Y)-t\right)$
$\displaystyle\overset{\textrm{Th }~{}\ref{Che-Can}}{\leq}$
$\displaystyle\frac{{\rm Var}(Y)}{{\rm Var}(Y)+t^{2}}$ $\displaystyle=$
$\displaystyle\frac{1}{1+\frac{t^{2}}{{\rm Var}(Y)}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{3}.$

Consider now $\mathcal{B}$ the event
$X\geq\left(1-\left(1-\frac{1}{2}\epsilon\right)\epsilon^{k}\right)\delta\mathrm{Opt}^{*}$.
Our basic assumption is to consider $\delta$, $k$ and $\epsilon$ constants,
and we can certainly assume that
$n\geq\frac{16\exp\left(a_{k,\epsilon}\right)}{\epsilon^{k+2}}$, since
otherwise we obtain an optimal solution for the set multicover problem in
polynomial time.
Choosing $\beta=\frac{1}{2}\epsilon^{k+1}$ we have

$\displaystyle(1+\beta)(1-\epsilon^{k})$ $\displaystyle=$ $\displaystyle
1-\epsilon^{k}+\frac{1}{2}\epsilon^{k+1}-\frac{1}{2}\epsilon^{2k+1}$
$\displaystyle=$ $\displaystyle
1-\epsilon^{k}\left(1-\frac{1}{2}\epsilon+\frac{1}{2}\epsilon^{k+1}\right)$
$\displaystyle\leq$ $\displaystyle
1-\left(1-\frac{1}{2}\epsilon\right)\epsilon^{k}.$

Note that
$\epsilon\in\left[\frac{\delta-1}{2\delta},\left(\frac{\delta-1}{2\delta}\right)^{\frac{1}{k}}\right]$
therewith $1-\epsilon^{k}\geq
1-\frac{\delta-1}{2\delta}=\frac{\delta+1}{2\delta}>\frac{1}{2}$.
We thus get

$\displaystyle\Pr\left(\mathcal{B}\right)$ $\displaystyle\leq$
$\displaystyle\Pr\left(X\geq(1+\beta)\cdot(1-\epsilon^{k})\delta\mathrm{Opt}^{*}\right)$
$\displaystyle\overset{\textrm{Th }~{}\ref{Doerr}}{\leq}$
$\displaystyle\exp\left(-\frac{\beta^{2}(1-\epsilon^{k})\delta\mathrm{Opt}^{*}}{3}\right)$
$\displaystyle\overset{\textrm{Lem.}\ref{lemma:random}(iv)}{\leq}$
$\displaystyle\exp\left(-\frac{\epsilon^{2k+2}(1-\epsilon^{k})\delta
n(b-1)}{12\ell}\cdot\frac{6\ell}{(b-1)\delta\epsilon^{k}\times\exp\left(a_{k,\epsilon}\right)}\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\epsilon^{k+2}(1-\epsilon^{k})n}{2\exp\left(a_{k,\epsilon}\right)}\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\epsilon^{k+2}n}{4\exp\left(a_{k,\epsilon}\right)}\right)$
$\displaystyle\leq$ $\displaystyle\exp\left(-4\right).$

Therefore it holds that

$\displaystyle\Pr\left(\overline{\mathcal{A}}\cap\overline{\mathcal{B}}\right)$
$\displaystyle\geq$ $\displaystyle
1-\left(\frac{1}{3}+\exp\left(-4\right)\right),$ (5)

where $\overline{\mathcal{A}}$ and $\overline{\mathcal{B}}$ denote the
complement events of $\mathcal{A}$ and $\mathcal{B}$ respectively. We conclude
that

$\displaystyle\Pr\left(\mathcal{C}\right)$ $\displaystyle=$
$\displaystyle\Pr\left(|C|\leq\left(1-\frac{1}{2}\left(1-\epsilon\right)\epsilon^{k}\right)\delta\mathrm{Opt}^{*}\right)$
$\displaystyle=$
$\displaystyle\Pr\left(|C|\leq\left(1-\left(1-\frac{1}{2}\epsilon\right)\epsilon^{k}+\frac{1}{2}\epsilon^{k}\right)\delta\mathrm{Opt}^{*}\right)$
$\displaystyle\overset{(\ref{expection})}{\geq}$
$\displaystyle\Pr\left(X+n-Y\leq\left(1-\left(1-\frac{1}{2}\epsilon\right)\epsilon^{k}+\frac{1}{2}\epsilon^{k}\right)\delta\mathrm{Opt}^{*}\right)$
$\displaystyle\geq$
$\displaystyle\Pr\left(X\leq\left(1-\left(1-\frac{1}{2}\epsilon\right)\epsilon^{k}\right)\delta\mathrm{Opt}^{*}\text{\
and\ }n-Y\leq\frac{1}{2}\epsilon^{k}\delta\mathrm{Opt}^{*}\right)$
$\displaystyle\geq$
$\displaystyle\Pr\left(X\leq\left(1-\left(1-\frac{1}{2}\epsilon\right)\epsilon^{k}\right)\delta\mathrm{Opt}^{*}\text{\
and\ }Y\geq n-\frac{1}{2}\epsilon^{k}\delta\mathrm{Opt}^{*}\right)$
$\displaystyle\geq$
$\displaystyle\Pr\left(X\leq\left(1-\left(1-\frac{1}{2}\epsilon\right)\epsilon^{k}\right)\delta\mathrm{Opt}^{*}\text{\
and\ }Y\geq n-n\exp\left(-2a_{k,\epsilon}\right)-t\right)$ $\displaystyle\geq$
$\displaystyle\Pr\left(X\leq\left(1-\left(1-\frac{1}{2}\epsilon\right)\epsilon^{k}\right)\delta\mathrm{Opt}^{*}\text{\
and\ }Y\geq n(1-\exp\left(-2a_{k,\epsilon}\right))-t\right)$
$\displaystyle\overset{(\ref{Intersection})}{\geq}$ $\displaystyle
1-\left(\frac{1}{3}+\exp\left(-4\right)\right)$ $\displaystyle\geq$
$\displaystyle 0.65.$

$\Box$
Remark 2. The proof above gives for $k=2$ and $\epsilon=\frac{1}{2}$ an
approximation ratio of
$\max\left\\{\frac{15}{16}\delta,\left(1-\frac{(b-1)\exp\left(\frac{3\delta+1}{8}\right)}{72\ell}\right)\delta\right\\}$.
Note that
$\frac{\delta-1}{2\delta}<\frac{1}{2}<\left(\frac{\delta-1}{2\delta}\right)^{\frac{1}{2}}$
therewith the condition of Theorem 5 on $\epsilon$ is satisfied.

As mentioned above our performance guaranty improves over the ratio presented
by Srivastav et al [7], and this without restriction on the parameter $\ell$.
Namely, for $\delta\geq 13$ we have

$\displaystyle 11(\delta-1)<\exp\left(\frac{3\delta+1}{8}\right)$
$\displaystyle\Rightarrow$
$\displaystyle\frac{11(\delta-1)}{72\ell}<\frac{\exp\left(\frac{3\delta+1}{8}\right)}{72\ell}$
$\displaystyle\overset{b-1\geq 1}{\Rightarrow}$
$\displaystyle\frac{11(\Delta-b)}{72\ell}<\frac{(b-1)\exp\left(\frac{3\delta+1}{8}\right)}{72\ell}$
$\displaystyle\Rightarrow$
$\displaystyle\left(1-\frac{(b-1)\exp\left(\frac{3\delta+1}{8}\right)}{72\ell}\right)\delta<\left(1-\frac{11(\Delta-b)}{72\ell}\right)\delta.$

##  4 Lower Bound

One of the features of the proof is the duality of hypergraphs. In dual
hypergraphs, vertices and edges just swap the roles. So the set multicover
problem in dual hypergraphs becomes as follows: find a minimum cardinality set
$C\subseteq V$ such that for every $E\in\mathcal{E}$ it holds $|E\cap C|\geq
b$. This problem is known as the $b$-vertex cover problem and we have that the
set multicover problem in $\Delta$-regular hypergraphs is equivalent to the
$b$-vertex cover problem in $\Delta$-uniform hypergraphs.

###### Theorem 6

Let $\epsilon>0$, $\Delta$ and $\bf b\in\mathbb{N}_{0}^{n}$ be given and
$b=\min_{i}b_{i}$. Then, it is NP-hard to approximate the set multicover
problem on $\Delta$-regular hypergraphs within a factor of
$\Delta-b-\epsilon$.

_Proof_. Assume, for a contradiction, that the theorem is false. Then there
exists an algorithm $\mathcal{A}$ that returns a
$(\Delta-b-\epsilon)$-approximation in polynomial time for the $b$-vertex
cover problem on $\Delta$-uniform hypergraphs.

We give a reduction of the minimum vertex cover problem on $\Delta$-uniform
hypergraphs to the $b$-vertex cover problem on $\Delta+b-1$-uniform
hypergraphs.

Let $\tilde{\mathcal{H}}=(V,\mathcal{E})$ be a $\Delta$-uniform hypergraph and
let $\alpha=\frac{2}{\epsilon}(\Delta-1-\epsilon)(b-1)$.
Now we consider the following algorithm:

  * 1.

Consider all subsets $T\subseteq V$ with $|T|\leq\alpha$. Check if any of
these subsets is a vertex cover in $\tilde{\mathcal{H}}$. If it’s the case
then return the smallest one of them, else go to step 2.

  * 2.

Add $b-1$ vertices $v_{1},\ldots,v_{b-1}$ to $V$. Define for every hyper-edge
$E$ a new edge $E^{\ast}:=E\cup\\{v_{1},\ldots,v_{b-1}\\}$ and the set
$\mathcal{E}^{\ast}:=\\{E^{\ast}|E\in\mathcal{E}\\}$. Finally set
$\mathcal{H}=(V\cup\\{v_{1},\ldots,v_{b-1}\\},\mathcal{E}^{\ast})$. We execute
$\mathcal{A}$ on $\mathcal{H}$. Return $T:=\mathcal{A}(\mathcal{H})\cap V$.

#### Claim

The algorithm given above returns a vertex cover in $\tilde{\mathcal{H}}$ in
polynomial-time with an approximation ratio of $\Delta-1-\frac{\epsilon}{2}$.

_Proof_.
Correctness and approximation ratio. If $T$ is selected by the algorithm in
step $1$ then $T$ is an optimal vertex cover in $\tilde{\mathcal{H}}$.
If $T$ is selected by the algorithm in step $2$ then
$\mathcal{A}(\mathcal{H})=T\cup K$ for some
$K\subset\\{v_{1},\ldots,v_{b-1}\\}$. Note that $T$ and $K$ are disjoint sets.
Consider an edge $E\in\mathcal{E}$. Because $\mathcal{A}(\mathcal{H})$ is a
$b$-vertex cover in $\mathcal{H}$, we have $|\mathcal{A}(\mathcal{H})\cap
E^{\ast}|=|T\cap E^{\ast}|+|K\cap E^{\ast}|\geq b$. Since $T\cap
E^{\ast}=T\cap E$ and $|K\cap E^{\ast}|\leq b-1$, it follows that $|T\cap
E|\geq 1$. Hence $T$ is a vertex cover in $\tilde{\mathcal{H}}$.
Now, let $C$ and $C^{\prime}$ denote a minimum vertex cover in
$\tilde{\mathcal{H}}$ and a minimum $b$-vertex cover in $\mathcal{H}$,
respectively. Since $D^{{}^{\prime}}:=C\cup\\{v_{1},\ldots,v_{b-1}\\}$ is a
feasible $b$-vertex cover in $\mathcal{H}$, it holds that
$|C^{\prime}|\leq|C|+b-1$. On the other hand, it is clear that $\mathcal{H}$
is a $\left(\Delta+b-1\right)$-uniform hypergraph, and by the assumption we
get

$\displaystyle|\mathcal{A}(\mathcal{H})|$
$\displaystyle\leq\left((\Delta+b-1)-b-\epsilon\right)|C^{\prime}|$
$\displaystyle\leq(\Delta-1-\epsilon)|C|+(\Delta-1-\epsilon)(b-1)=(\Delta-1-\epsilon)|C|+\frac{\epsilon}{2}\alpha$
$\displaystyle\overset{|C|\geq\alpha}{\leq}(\Delta-1-\frac{\epsilon}{2})|C|.$

Since $|T|=|\mathcal{A}(\mathcal{H})\cap V|\leq|\mathcal{A}(\mathcal{H})|$, it
follows that $|T|\leq(\Delta-1-\frac{\epsilon}{2})|C|$.

Running time. In step 1 we test at most $n^{\alpha}$ sets of vertices to be a
vertex cover in $\tilde{\mathcal{H}}$. Since
$\alpha=\frac{2}{\epsilon}(\Delta-1-\epsilon)(b-1)$ is a constant, the running
time in this step is polynomial. In step 2 we add a constant number of
vertices to $V$ and execute the algorithm $\mathcal{A}$. Hence the algorithm
runs in polynomial time in both steps.

With Claim 1 there is a factor $\Delta-1-\frac{\epsilon}{2}$ approximation
algorithm for the minimum vertex cover problem on $\Delta$-uniform
hypergraphs, which contradicts the statement of Theorem 3. $\Box$

##  5 The $\frac{\ln_{2}(n+1)}{2b}$-Integrality Gap

The integrality gap for set multicover problem is defined as the supremum of
the ratio $\frac{{\rm Opt}_{{\bf b}}(\mathcal{H})}{{\rm Opt}^{*}_{{\bf
b}}(\mathcal{H})}$ over all instances $\cal{H}$ of the problem. In this
section we give a slight modification of the proof presented in [22] for the
integrality gap. We present in the following a specific class of instances of
the set multicover problem, where ${\bf b}:=(b,\ldots,b)\in\mathbb{N}^{n}$ for
which the integrality gap is at least $\frac{\ln_{2}(n+1)}{2b}$.

###### Theorem 7

let ${\bf b}:=(b,\ldots,b)\in\mathbb{N}^{n}$. The integrality gap of the set
multicover problem is at least $\frac{\ln_{2}(n+1)}{2b}$.

Define $V=F_{2}^{k}\backslash\\{0\\}$ as the set of all $k$-dimensional non-
zero vectors with component values of $\mathbb{Z}_{2}=\\{0,1\\}$ for a fixed
integer $k$ and we define ${\cal E}$ as a collection of the sets
$E_{v}=\\{u\in V:<v,u>\equiv 1[2]\\}$ for each $v\in V$, where $<.\,,.>$ is
the usual dot product in $V$.

We remark that each element $v\in V$ is contained in exactly half of the sets
of ${\cal E}$ therewith the hypergraph ${\cal H}=(V,{\cal E})$ is regular and
$n=|V|=2^{k}-1$.

###### Lemma 4

Let ${\cal H}=(V,{\cal E})$ the hypergraph defined and ${\bf
b}\in\mathbb{N}_{\geq 1}^{n}$. It holds that the vector $x=(\frac{2b}{|{\cal
E}|},\ldots,\frac{2b}{|{\cal E}|})$ is a feasible solution for
LP($\Delta,\,{\bf b}$).

_Proof_. It is clear that $x=(\frac{2b}{|{\cal E}|},\ldots,\frac{2b}{|{\cal
E}|})$ is a feasible solution for lP$(\Delta,{\bf b})$, namely since
$\mathcal{H}$ is regular with $\Delta=\frac{|{\cal E}|}{2}$ we have for every
$i\in\\{1,\ldots,n\\}$

$\sum_{E\in\Gamma(v_{i})}\frac{2b}{|{\cal E}|}=\frac{2b}{|{\cal
E}|}\cdot\Delta=\frac{2b}{|{\cal E}|}\cdot\frac{|{\cal E}|}{2}\geq b$

therewith $\mathrm{Opt}^{*}\leq 2b$. $\Box$

###### Lemma 5

The optimal integral solution to the previous LP formulation of the set
multicover problem requires at least $k$ sets.

_Proof_. Let $\\{E_{v_{1}},E_{v_{2}}\ldots E_{v_{t}}\\}$ a collection of sets
such that ${\bigcup}_{i\in[t]}E_{v_{i}}=F_{2}^{k}\backslash\\{0\\}$. This
implies that the intersection of their complements contains exactly the zero
vector, i.e., ${\bigcap}_{i\in[t]}E_{v_{i}}^{C}=\\{0\\}$. It follows that $0$
is the only solution in $F_{2}^{k}$ of the system

$<x,v_{i}>\equiv 0[2],\quad\forall i\in[t]$

Then it holds that $t\geq k$, since the dimension of $F_{2}^{k}$ is $k$ while
the number of the equations in the system is $t$. From this we conclude
$\mathrm{Opt}\geq\ln_{2}(n+1)$. $\Box$

Proof of Theorem 7. Theorem 7 follows from Lemma 4 and Lemma 5. $\Box$

##  6 Future Work

We believe now that the conjecture of Peleg et al. holds in the general
setting. Hence proving the trueness of the conjecture remains a big challenge
for our future works.

## References

  * [1] R. Bar-Yehuda. _Using Homogeneous Weights for Approximating the Partial Cover Problem._ Journal of Algorithms, 39(2):137–144, 2001.
  * [2] I. Dinur, V. Guruswami, S. Khot, O. Regev, _A new multilayered PCP and the hardness of hypergraph vertex cover_ , SIAM J. Comput. 34 (5) 1129–1146, 2005.
  * [3] B. Doerr, F. (Eds.) Neumann. _Theory of Evolutionary Computation: Recent Developments in Discrete Optimization_. Springer Nature 2019.
  * [4] R. Duh, M. Fürer. _Approximating k-set cover by semi-local optimization._ in: Proc. 29th Annual Symposium on Theory on Computing, May, pp. 256–264, 1997.
  * [5] M. El Ouali, H. Fohlin, A. Srivastav. _An approximation algorithm for the partial vertex cover problem in hypergraphs_. Journal of Combinatorial Optimization, 31(2): 846–864, 2016.
  * [6] M. El Ouali, H. Fohlin, A. Srivastav. _A Randomised approximation algorithm for the hitting set problem_. Theoretical Computer Science 555: 23–34, 2014.
  * [7] M. El Ouali, P. Munstermann, A. Srivastav. _Randomized approximation for set multicover in hypergraphs_. Algorithmica, 74(2): 574–588, 2016.
  * [8] U. Feige. _A threshold of $\ln n$ for approximating set cover._ J. ACM, 45(4):634–652, 1998.
  * [9] T. Fujito, H. Kurahashi. _A Better-Than-Greedy Algorithm for k-Set Multicover._ In: 3rd International Workshop on Approximation and Online Algorithms, pp. 176–189, 2006.
  * [10] R. Gandhi, S. Khuller and A. Srinivasan. _Approximation Algorithms for Partial Covering Problems._ Journal of Algorithms, 53(1):55–84, 2004.
  * [11] N.G. Hall, D.S. Hochbaum. _A Fast Approximation Algorithm for the Multicovering Problem._ Discrete Applied Mathematics, 15:35–40, 1986.
  * [12] D.S. Hochbaum. _Approximation Algorithms for the Set Covering and Vertex Cover Problems._ SIAM J. Comput, 11(3):555–556, August 1982.
  * [13] D. S. Johnson. _Approximation Algorithms for Combinatorial Problems._ Journal of Computer and System Sciences, 9:256–278, 1974.
  * [14] R. KARP, _Reducibility among combinatorial problems._ In R.E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations, pp. 85–103. Plenum Press, New York, NY, 1972.
  * [15] S. Khot and O. Regev. _Vertex Cover Might be Hard to Approximate to Within 2-epsilon._ Journal of Computer and System Sciences, 74(3):335–349, 2008.
  * [16] C. Koufogiannakis, N.E. Young. _Greedy $\Delta$-approximation algorithm for covering with arbitrary constraints and submodular cost_. Algorithmica, 66(1), 113–152, 2013.
  * [17] L. Lovász. _On the Ratio of Optimal Integral and Fractional Covers._ Discrete Mathematics, 13(4):383–390, 1975.
  * [18] R. Motwani, P. Raghavan. _Randomized Algorithms_. Cambridge University Press 1995.
  * [19] D. Peleg, G. Schechtman, A. Wool. _Randomized Approximation of Bounded Multicovering Problems._ Algorithmica, 18(1):44–66, 1997.
  * [20] D. Peleg, G. Schechtman, A. Wool. _Approximating bounded 0-1 integer linear programs._ In Proc. 2nd Israel Symp. on Theory of Computing Systems, pp. 69–77, Netanya, 1993.
  * [21] S. Rajagopalan, V. V. Vazirani. _Primal-dual RNC approximation algorithms for set cover and covering integer programs_. SIAM J. Comput., 28(2), 525–540, 1998.
  * [22] V. V. Vazirani. _Approximation Algorithms_ , pp. 108–112, Springer 2001.