Refine
Document Type
- ZIB-Report (3)
Language
- English (3)
Has Fulltext
- yes (3) (remove)
Is part of the Bibliography
- no (3)
Keywords
- Hall condition (1)
- Matchings in hypergraphs (1)
- Normal hypergraphs (1)
Institute
- Mathematical Optimization (3) (remove)
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})$.