Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 1 von 17
Zurück zur Trefferliste

An Approximation Result for Matchings in Partitioned Hypergraphs

Zitieren Sie bitte immer diese 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})$.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Isabel BeckenbachORCiD, Ralf BorndörferORCiD
Dokumentart:ZIB-Report
Jahr der Erstveröffentlichung:2014
Schriftenreihe (Bandnummer):ZIB-Report (14-30)
Verlagspublikation:Appeared in: Operations Research Proceedings 2014 (2016) pp. 31-36.
DOI:https://doi.org/10.1007/978-3-319-28697-6_5
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.