Approximation of set multi-cover via hypergraph matching.

For a given b ∈ N n and a hypergraph H = (V , E) with maximum degree Δ, the b -set multicover problem which we are concerned with in this paper may be stated as follows: find a minimum cardinality subset C ⊆ E such that no vertex v i ∈ V is contained in less than b i hyperedges of C. Peleg, Schechtman, and Wool (1997) conjectured that for any fixed Δ and b = min i ⁡ b i , the problem cannot be approximated with a ratio strictly smaller than δ : = Δ − b + 1 , unless P = NP. In this paper, we show that the conjecture of Peleg et al. is not true on ℓ -uniform hypergraphs by presenting a polynomial-time approximation algorithm based on a matching/covering duality for hypergraphs due to Ray-Chaudhuri (1960), which we convert into an approximative form. The given algorithm yields a ratio smaller than (1 − b (ℓ + 1) Δ) Δ b. Moreover, we prove that the lower bound conjectured by Peleg et al. holds for regular hypergraphs under the unique games conjecture. [ABSTRACT FROM AUTHOR]