liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
An approximation algorithm for the partial vertex cover problem in hypergraphs
University of Kiel, Germany.
Linköping University, Department of Clinical and Experimental Medicine, Division of Clinical Sciences. Region Östergötland, Center for Health and Developmental Care, Regional Cancer Center South East Sweden. Linköping University, Faculty of Medicine and Health Sciences.
University of Kiel, Germany.
2016 (English)In: Journal of combinatorial optimization, ISSN 1382-6905, E-ISSN 1573-2886, Vol. 31, no 2, 846-864 p.Article in journal (Refereed) PublishedText
Abstract [en]

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(.)

Place, publisher, year, edition, pages
SPRINGER , 2016. Vol. 31, no 2, 846-864 p.
Keyword [en]
Combinatorial optimization; Approximation algorithms; Hypergraphs; Vertex cover; Probabilistic methods
National Category
Clinical Medicine
Identifiers
URN: urn:nbn:se:liu:diva-125307DOI: 10.1007/s10878-014-9793-2ISI: 000368686900024OAI: oai:DiVA.org:liu-125307DiVA: diva2:906366
Available from: 2016-02-24 Created: 2016-02-19 Last updated: 2016-02-24

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Fohlin, Helena
By organisation
Division of Clinical SciencesRegional Cancer Center South East SwedenFaculty of Medicine and Health Sciences
In the same journal
Journal of combinatorial optimization
Clinical Medicine

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 919 hits
ReferencesLink to record
Permanent link

Direct link