Approximation algorithm for the multicovering problem

Let H = (V, epsilon) be a hypergraph with maximum edge size l and maximum degree Delta. For a given positive integers b(v), v is an element of V, a set multicover in H is a set of edges C subset of epsilon 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 for any fixed Delta and b := min(v is an element of V) b(v), the problem of set multicover is not approximablewithin a ratio less than delta :=Delta-b+1, unlessP = 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 {148/149 delta, (1 - (b-1)e(delta/4)/94l)delta} for b >= 2 and delta >= 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 l. Moreover we present a further polynomial time algorithm with an approximation ratio of 5/6 delta for hypergraphs with l <= (1 + epsilon)(l) over bar for any fixed epsilon is an element of [0, 1/2], where (l) over bar 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.