umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The b-Matching Problem in Hypergraphs: Hardness and Approximability
Computer Science Institute, Christian-Albrechts-University of Kiel, Germany.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
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, Published paper (Refereed)
Abstract [en]

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.
Series
Lecture Notes in Computer Science, 7402
Keyword [en]
Hypergraphs, matching, L-reduction, Boolean satisfiability, randomized rounding, MAX-SNP-hardness
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-84483DOI: 10.1007/978-3-642-31770-5Libris ID: 13537064ISBN: 9783642317705 (print)OAI: oai:DiVA.org:umu-84483DiVA: diva2:684499
Conference
6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012)
Available from: 2014-01-08 Created: 2014-01-08 Last updated: 2014-09-23

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Jäger, Gerold

Search in DiVA

By author/editor
Jäger, Gerold
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 55 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf