2021/01/22 by Gorgi, Abbass, Ouali, Mourad El, Srivastav, Anand +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2101.09080
Let H=(V,E) be a hypergraph with maximum edge size ℓ and maximum degree Δ. For given numbers bv∈ ℕ≥ 2, v∈ V, a set multicover in H is a set of edges C ⊆ E such that every vertex v in V belongs to at least bv edges in C. Set multicover is the problem of finding a minimum-cardinality set multicover. Peleg, Schechtman and Wool conjectured that unless \calP =\calNP, for any fixed Δ and b:=minv∈ Vbv, no polynomial-time approximation algorithm for the Set multicover problem has an approximation ratio less than δ:=Δ-b+1. Hence, it's a challenge to know whether the problem of set multicover is not approximable within a ratio of βδ with a constant β<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\ (15)/(16)δ, (1- ((b-1)exp(( 3δ+1)/(8)))/(72 ℓ) )δ\. The crucial fact is not only that our result improves over the approximation ratio presented by Srivastav et al (Algorithmica 2016) for any δ≥ 13, but it's more general since we set no restriction on the parameter ℓ. Furthermore, we prove that it is NP-hard to approximate the Set multicover problem on Δ-regular hypergraphs within a factor of (δ-1-ε). Moreover we show that the integrality gap for the Set multicover problem is at least \fracln2(n+1)2b, which for constant b is Ω(ln n ).