Exploring foci of:
arXiv (Cornell University)
Repeated randomized algorithm for the Multicovering Problem
January 2021 • Abbass Gorgi, Mourad El Ouali, Anand Srivastav, Mohamed Hachimi
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 poly…
Combinatorics
Mathematics
Vertex (Graph Theory)
Discrete Mathematics
Data Mining
Computer Science