The b-Matching Problem in Hypergraphs: Hardness and Approximability
2012 (English)In: Proceedings of 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012) / [ed] Guohui Lin, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2012, 200-211 p.Conference paper (Refereed)
In this paper we analyze the maximum cardinality -matching problem in -uniform hypergraphs with respect to the complexity class MAX-SNP, where -matching is defined as follows: for given and a hypergraph a subset with maximum cardinality is sought so that no vertex is contained in more than hyperedges of . We show that if the maximum degree of the vertices is bounded by a constant , this problem has no approximation scheme, unless . This result generalizes a result of Kann from to the case that with . Furthermore, we extend a result of Srivastav and Stangier, who gave an approximation algorithm for the unweighted b-matching problem.
Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer Berlin-Heidelberg , 2012. 200-211 p.
, Lecture Notes in Computer Science, 7402
Hypergraphs, matching, L-reduction, Boolean satisfiability, randomized rounding, MAX-SNP-hardness
IdentifiersURN: urn:nbn:se:umu:diva-84483DOI: 10.1007/978-3-642-31770-5ISBN: 9783642317705OAI: oai:DiVA.org:umu-84483DiVA: diva2:684499
6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012)