Repeated randomized algorithm for the Multicovering Problem

arXiv2101.09080MaRDI QIDQ6358802FDOQ6358802

Authors: Abbass Gorgi, Mourad El Ouali, Anand Srivastav, Mohamed Hachimi 

Publication date: 22 January 2021

Abstract: Let $mathcalH=(V,mathcalE)$ be a hypergraph with maximum edge size $ell$ and maximum degree $Delta$. For given numbers $b_{v}inmathbb{N}_{geq2}$, $vinV$, a set multicover in $mathcalH$ is a set of edges $CsubseteqmathcalE$ 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 $calP=calNP$, for any fixed $Delta$ and $b:=mi{n}_{vinV}{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 $$ with a constant $$. 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 $maxleftfrac1516delta,left(1-frac(b-1)expleft(frac3delta+18ight)72ellight)deltaight$. The crucial fact is not only that our result improves over the approximation ratio presented by Srivastav et al (Algorithmica 2016) for any $deltageq13$, 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 $fracl{n}_2(n+1)2b$, which for constant $b$ is $Omega(lnn)$.

This page was built for publication: Repeated randomized algorithm for the Multicovering Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6358802)