Repeated randomized algorithm for the Multicovering Problem Article Swipe

MAKE IMPACT

Abbass Gorgi , Mourad El Ouali , Anand Srivastav , Mohamed Hachimi · YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2101.09080

Let $\mathcal{H}=(V,\mathcal{E})$ be a hypergraph with maximum edge size $\ell$ and maximum degree $Δ$. 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 $\cal{P} =\cal{NP}$, for any fixed $Δ$ and $b:=\min_{v\in V}b_{v}$, 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\left\{ \frac{15}{16}δ, \left(1- \frac{(b-1)\exp\left(\frac{ 3δ+1}{8}\right)}{72 \ell} \right)δ\right\}$. The crucial fact is not only that our result improves over the approximation ratio presented by Srivastav et al (Algorithmica 2016) for any $δ\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 $Δ$-regular hypergraphs within a factor of $(δ-1-ε)$. 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 $Ω(\ln n )$.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2101.09080

PDF

https://arxiv.org/pdf/2101.09080

OA Status

green

References

19

Related Works

10

OpenAlex ID

https://openalex.org/W3123672655

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W3123672655

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2101.09080

Digital Object Identifier

Title

Repeated randomized algorithm for the Multicovering Problem

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2021

Year of publication

Publication date

2021-01-22

Full publication date if available

Authors

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

List of authors in order

Landing page

https://arxiv.org/abs/2101.09080

Publisher landing page

PDF URL

https://arxiv.org/pdf/2101.09080

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2101.09080

Direct OA link when available

Concepts

Combinatorics, Mathematics, Hypergraph, Approximation algorithm, Vertex (graph theory), Cardinality (data modeling), Randomized algorithm, Deterministic algorithm, Discrete mathematics, Graph, Data mining, Computer science

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

References (count)

19

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload