# Approximation algorithm for the Multicovering Problem

arXiv: https://arxiv.org/abs/2003.06936 · HTML: https://mlsanity.com/paper/2003.06936/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Mar 2020.

## Built on by (most cited first, 1 of 1)

- [COMRECGC: Global Graph Counterfactual Explainer through Common Recourse](https://mlsanity.com/paper/2505.07081/) (2025)

## Abstract (arXiv)

Let H=(V,E) be a hypergraph with maximum edge size ℓ and maximum degree Delta. For given numbers bv∈ mathbbN≥ 2, v∈ V, a set multicover in H is a set of edges C subseteq 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 for any fixed Delta and b:=minv∈ Vbv, the problem of sbmultcov is not approximable within a ratio less than δ:=Delta-b+1, unless P =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  maxleft frac148149δ, left(1- frac (b-1)e^fracδ494ℓ right)δ right. Our result not only improves over the approximation ratio presented by Srivastav et al (Algorithmica 2016) but it's more general since we set no restriction on the parameter ℓ. Moreover we present a further polynomial time algorithm with an approximation ratio of frac56δ for hypergraphs with ℓ≤ (1+ε)barℓ for any fixed ε ∈ [0,frac12], where 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.