Approximation algorithm for the multicovering problem

Let $$\mathcal {H}=(V,\mathcal {E})$$ H = ( V , E ) be a hypergraph with maximum edge size $$\ell $$ ℓ and maximum degree $$\varDelta $$ Δ . For a given positive integers $$b_v$$ b v , $$v\in V$$ v ∈ V , a set multicover in $$\mathcal {H}$$ H is a set of edges $$C \subseteq \mathcal {E}$$ C ⊆ E such that every vertex v in V belongs to at least $$b_v$$ b v edges in C. Set multicover is the problem of finding a minimum-cardinality set multicover. Peleg, Schechtman and Wool conjectured that for any fixed $$\varDelta $$ Δ and $$b:=\min _{v\in V}b_{v}$$ b : = min v ∈ V b v , the problem of set multicover is not approximable within a ratio less than $$\delta :=\varDelta -b+1$$ δ : = Δ - b + 1 , unless $$\mathcal {P}=\mathcal {NP}$$ P = NP . Hence it’s a challenge to explore for which classes of hypergraph the conjecture doesn’t hold. We present a polynomial time algorithm for the set multicover problem which combines a deterministic threshold algorithm with conditioned randomized rounding steps. Our algorithm yields an approximation ratio of $$\max \left\{ \frac{148}{149}\delta , \left( 1- \frac{ (b-1)e^{\frac{\delta }{4}}}{94\ell } \right) \delta \right\} $$ max 148 149 δ , 1 - ( b - 1 ) e δ 4 94 ℓ δ for $$b\ge 2$$ b ≥ 2 and $$\delta \ge 3$$ δ ≥ 3 . Our result not only improves over the approximation ratio presented by El Ouali et al. (Algorithmica 74:574, 2016) but it’s more general since we set no restriction on the parameter $$\ell $$ ℓ . Moreover we present a further polynomial time algorithm with an approximation ratio of $$\frac{5}{6}\delta $$ 5 6 δ for hypergraphs with $$\ell \le (1+\epsilon )\bar{\ell }$$ ℓ ≤ ( 1 + ϵ ) ℓ ¯ for any fixed $$\epsilon \in [0,\frac{1}{2}]$$ ϵ ∈ [ 0 , 1 2 ] , where $$\bar{\ell }$$ ℓ ¯ is the average edge size. The analysis of this algorithm relies on matching/covering duality due to Ray-Chaudhuri (1960), which we convert into an approximative form. The second performance disprove the conjecture of Peleg et al. for a large subclass of hypergraphs.