An Approximation Result for Matchings in Partitioned Hypergraphs

  • We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most $2\sqrt{d}$ for partitioned hypergraphs with parts of size $\leq d$. Furthermore, we show that this bound cannot be improved to $\mathcal{O}(d^{0.5-\epsilon})$.

Export metadata

  • Export Bibtex
Metadaten
Author:Isabel Beckenbach, Ralf Borndörfer
Document Type:In Proceedings
Parent Title (English):Operations Research Proceedings 2014
First Page:31
Last Page:36
Publisher:Springer International Publishing
Date of first Publication:2016/02/21
Pagenumber:6
Preprint:urn:nbn:de:0297-zib-51083
DOI:http://dx.doi.org/10.1007/978-3-319-28697-6_5

$Rev: 13581 $