An approximation algorithm for the partial vertex cover problem in hypergraphs.

El Ouali, M., Fohlin, H. and Srivastav, Anand (2016) An approximation algorithm for the partial vertex cover problem in hypergraphs. Journal of Combinatorial Optimization, 31 (2). pp. 846-864. DOI 10.1007/s10878-014-9793-2.

Full text not available from this repository.

Supplementary data:


Let be a hypergraph with set of vertices and set of (hyper-)edges . Let be the maximum size of an edge, be the maximum vertex degree and be the maximum edge degree. The -partial vertex cover problem in hypergraphs is the problem of finding a minimum cardinality subset of vertices in which at least hyperedges are incident. For the case of and constant it known that an approximation ratio better than cannot be achieved in polynomial time under the unique games conjecture (UGC) (Khot and Ragev J Comput Syst Sci, 74(3):335-349, 2008), but an -approximation ratio can be proved for arbitrary (Gandhi et al. J Algorithms, 53(1):55-84, 2004). The open problem in this context has been to give an -ratio approximation with , as small as possible, for interesting classes of hypergraphs. In this paper we present a randomized polynomial-time approximation algorithm which not only achieves this goal, but whose analysis exhibits approximation phenomena for hypergraphs with not visible in graphs: if and are constant, and , we prove for -uniform hypergraphs a ratio of , which tends to the optimal ratio 1 as tends to . For the larger class of hypergraphs where , is not constant, but is a constant, we show a ratio of . Finally for hypergraphs with non-constant , but constant , we get a ratio of for , leaving open the problem of finding such an approximation for k < m/4(.)

Document Type: Article
Additional Information: Times Cited: 1 El Ouali, Mourad Fohlin, Helena Srivastav, Anand
Keywords: Combinatorial optimization Approximation algorithms Hypergraphs Vertex cover Probabilistic methods
Research affiliation: Kiel University
Kiel University > Kiel Marine Science
OceanRep > The Future Ocean - Cluster of Excellence
Refereed: Yes
Open Access Journal?: No
DOI etc.: 10.1007/s10878-014-9793-2
ISSN: 1382-6905
Projects: Future Ocean
Date Deposited: 19 Mar 2017 08:07
Last Modified: 23 Sep 2019 20:53

Actions (login required)

View Item View Item