- Treffer 1 von 1
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})$.
Verfasserangaben: | Isabel BeckenbachORCiD, Ralf BorndörferORCiD |
---|---|
Dokumentart: | Konferenzbeitrag |
Titel des übergeordneten Werkes (Englisch): | Operations Research Proceedings 2014 |
Erste Seite: | 31 |
Letzte Seite: | 36 |
Verlag: | Springer International Publishing |
Datum der Erstveröffentlichung: | 21.02.2016 |
Seitenzahl: | 6 |
Preprint: | urn:nbn:de:0297-zib-51083 |
DOI: | https://doi.org/10.1007/978-3-319-28697-6_5 |