Approximation algorithm for the multicovering problem

Abbass Gorgi (), Mourad El Ouali (), Anand Srivastav () and Mohamed Hachimi ()
Additional contact information
Abbass Gorgi: University Ibn Zohr
Mourad El Ouali: Christian Albrechts University
Anand Srivastav: Christian Albrechts University
Mohamed Hachimi: University Ibn Zohr

Journal of Combinatorial Optimization, 2021, vol. 41, issue 2, No 10, 433-450

Abstract: Abstract Let $$\mathcal {H}=(V,\mathcal {E})$$ H = ( V , E ) be a hypergraph with maximum edge size $$\ell $$ ℓ and maximum degree $$\varDelta $$ Δ . For a given positive integers $$b_v$$ b v , $$v\in V$$ v ∈ V , a set multicover in $$\mathcal {H}$$ H is a set of edges $$C \subseteq \mathcal {E}$$ C ⊆ E such that every vertex v in V belongs to at least $$b_v$$ b v edges in C. Set multicover is the problem of finding a minimum-cardinality set multicover. Peleg, Schechtman and Wool conjectured that for any fixed $$\varDelta $$ Δ and $$b:=\min _{v\in V}b_{v}$$ b : = min v ∈ V b v , the problem of set multicover is not approximable within a ratio less than $$\delta :=\varDelta -b+1$$ δ : = Δ - b + 1 , unless $$\mathcal {P}=\mathcal {NP}$$ 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 $$\max \left\{ \frac{148}{149}\delta , \left( 1- \frac{ (b-1)e^{\frac{\delta }{4}}}{94\ell } \right) \delta \right\} $$ max 148 149 δ , 1 - ( b - 1 ) e δ 4 94 ℓ δ for $$b\ge 2$$ b ≥ 2 and $$\delta \ge 3$$ δ ≥ 3 . Our result not only improves over the approximation ratio presented by El Ouali et al. (Algorithmica 74:574, 2016) but it’s more general since we set no restriction on the parameter $$\ell $$ ℓ . Moreover we present a further polynomial time algorithm with an approximation ratio of $$\frac{5}{6}\delta $$ 5 6 δ for hypergraphs with $$\ell \le (1+\epsilon )\bar{\ell }$$ ℓ ≤ ( 1 + ϵ ) ℓ ¯ for any fixed $$\epsilon \in [0,\frac{1}{2}]$$ ϵ ∈ [ 0 , 1 2 ] , where $$\bar{\ell }$$ ℓ ¯ 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.

Keywords: Integer linear programs; Hypergraphs; Approximation algorithm; Randomized rounding; Set cover and set multicover; $$\mathbf{k}$$ k -matching (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00688-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:2:d:10.1007_s10878-020-00688-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00688-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().