An Approximation Result for Matchings in Partitioned Hypergraphs

Isabel Beckenbach () and Ralf Borndörfer ()
Additional contact information
Isabel Beckenbach: Zuse Institut Berlin
Ralf Borndörfer: Zuse Institut Berlin

A chapter in Operations Research Proceedings 2014, 2016, pp 31-36 from Springer

Abstract: Abstract 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}$$ 2 d for partitioned hypergraphs with parts of size $$\le d$$ ≤ d . Furthermore, we show that this bound cannot be improved to $$\mathscr {O}(d^{0.5-\varepsilon })$$ O ( d 0.5 - ε ) .

Keywords: Perfect Matching Polytope; Maximum Part Size; Maximum Weight Matching Problem; Iterative Rounding Algorithm; Valid Inequalities (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-28697-6_5

Ordering information: This item can be ordered from
http://www.springer.com/9783319286976

DOI: 10.1007/978-3-319-28697-6_5

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().