An Approximation Result for Matchings in Partitioned Hypergraphs

Please always quote using this URN: urn:nbn:de:0297-zib-51083
  • 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})$.

Download full text files

Export metadata

Author:Isabel Beckenbach, Ralf BorndörferORCiD
Document Type:ZIB-Report
Year of first publication:2014
Series (Serial Number):ZIB-Report (14-30)
Published in:Appeared in: Operations Research Proceedings 2014 (2016) pp. 31-36.