Publication Date:
2022-03-11
Description:
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})$.
Language:
English
Type:
reportzib
,
doc-type:preprint
Format:
application/pdf