Approximation algorithm for the Multicovering Problem
| Autor: | Anand Srivastav, Mohamed Hachimi, Mourad El Ouali, Abbass Gorgi |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Hypergraph Control and Optimization Matching (graph theory) 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics Computer Science - Data Structures and Algorithms FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Time complexity Mathematics 021103 operations research Conjecture Applied Mathematics Duality (order theory) Approximation algorithm Computer Science Applications Vertex (geometry) Computational Theory and Mathematics 010201 computation theory & mathematics Combinatorics (math.CO) Randomized rounding |
| DOI: | 10.48550/arxiv.2003.06936 |
| Popis: | Let $$\mathcal {H}=(V,\mathcal {E})$$ be a hypergraph with maximum edge size $$\ell $$ and maximum degree $$\varDelta $$ . For a given positive integers $$b_v$$ , $$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 for any fixed $$\varDelta $$ and $$b:=\min _{v\in V}b_{v}$$ , the problem of set multicover is not approximable within a ratio less than $$\delta :=\varDelta -b+1$$ , unless $$\mathcal {P}=\mathcal {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\} $$ for $$b\ge 2$$ and $$\delta \ge 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 $$ for hypergraphs with $$\ell \le (1+\epsilon )\bar{\ell }$$ for any fixed $$\epsilon \in [0,\frac{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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|