Randomized Approximation for the Set Multicover Problem in Hypergraphs.

El Ouali, M., Munstermann, P. and Srivastav, Anand (2016) Randomized Approximation for the Set Multicover Problem in Hypergraphs. Algorithmica, 74 (2). pp. 574-588. DOI 10.1007/s00453-014-9962-9.

Full text not available from this repository.

Supplementary data:

Abstract

Let b is an element of N->= 1 and let H = (V, epsilon) be a hypergraph with maximum vertex degree Delta and maximum edge size l. A set b-multicover in H is a set of edges C subset of epsilon such that every vertex in V belongs to at least edges in C SET b-MULTICOVER is the problem of finding a set b-multicover of minimum cardinality, and for b=1 it is the fundamental set cover problem. Peleg et al. (Algorithmica 18(1):44-66, 1997) gave a randomized algorithm achieving an approximation ratio of delta . (1-(c/n)(1/delta)), where delta := Delta-b+1 and c > 0 is a constant. As this ratio depends on the instance size n and tends to delta as n tends to infinity, it remained an open problem whether an approximation ratio of delta alpha with a constant alpha < 1 can be proved. In fact, the authors conjectured that for any fixed Delta and b, the problem is not approximable within a ratio smaller than delta, unless p = NP. We present a randomized algorithm of hybrid type for SET b-MULTICOVER, b >= 2, combining LP-based randomized rounding with greedy repairing, and achieve an approximation ratio of delta. (1- 11(Delta-b)/72l)) for hypergraphs with maximum edge size l is an element of Omicron (max {(nb)(1/5),n(1/4)}) . In particular, for all hypergraphs where l is constant, we get an alpha delta-ratio with constant alpha < 1. Hence the above stated conjecture does not hold for hypergraphs with constant l and we have identified the boundedness of the maximum hyperedge size as a relevant parameter responsible for approximations below delta.

Document Type: Article
Additional Information: Times Cited: 0 El Ouali, Mourad Munstermann, Peter Srivastav, Anand
Keywords: Combinatorial optimization Approximation algorithms Randomized algorithm Hypergraphs Set cover and set multicover
Research affiliation: Kiel University
Kiel University > Kiel Marine Science
OceanRep > The Future Ocean - Cluster of Excellence
Refereed: Yes
Open Access Journal?: No
Publisher: American Medical Association
Projects: Future Ocean
Date Deposited: 16 Mar 2017 07:30
Last Modified: 23 Sep 2019 19:49
URI: https://oceanrep.geomar.de/id/eprint/36073

Actions (login required)

View Item View Item