OceanRep
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.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 |
Copyright 2023 | GEOMAR Helmholtz-Zentrum für Ozeanforschung Kiel | All rights reserved
Questions, comments and suggestions regarding the GEOMAR repository are welcomed
at bibliotheksleitung@geomar.de !