Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Experimental Validation of an Enhanced System Synthesis Approach Read chapter Read first chapter

2016 | OriginalPaper | Chapter

An Approximation Result for Matchings in Partitioned Hypergraphs

Authors : Isabel Beckenbach, Ralf Borndörfer

Published in: Operations Research Proceedings 2014

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Simulation of the System-Wide Impact of Power-to-Gas Energy Storages by Multi-stage Optimization
next chapter On Class Imbalance Correction for Classification Algorithms in Credit Scoring
Literature
1.
Beckenbach, I.: Special cases of the hypergraph assignment problem. Master Thesis, TU Berlin (2013)
2.
Berge, C.: Sur certains hypergraphes généralisant les graphes bipartites. In: Combinatorial Theory and its Applications, I (Proc. Colloq., Balatonfred, 1969), pp. 119–133. North-Holland, Amsterdam (1970)
3.
Borndörfer, R., Heismann, O.: The Hypergraph Assignment Problem. Technical Report, Zuse Institut, Berlin (2012)
4.
Chan, Y., Lau, L.: On linear and semidefinite programming relaxations for hypergraph matching. Math. Prog. 135(1–2), 123–148 (2012)CrossRef
5.
Füredi, Z., Kahn, J., Seymour, P.D.: On the fractional matching polytope of a hypergraph. Combinatorica 13(2), 167–180 (1993)CrossRef
6.
Halldórsson, M.M.: Approximations of weighted independent set and hereditary subset problems. Lect. Notes Comput. Sci. 1627, 261–270 (1999)CrossRef
7.
Halldórsson, M.M., Kratochvíl, J., Telle, J.A.: Independent sets with domination constraints. Discret. Appl. Math. 99, 39–54 (2000)CrossRef
8.
Hazan, E., Safra, M., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20–29 (2006)CrossRef
9.
Heismann, O.: The Hypergraph Assignment Problem. Ph.D. Thesis, TU Berlin (2014)
Metadata
Title
An Approximation Result for Matchings in Partitioned Hypergraphs
Authors
Isabel Beckenbach
Ralf Borndörfer
Copyright Year
2016
Book
Operations Research Proceedings 2014

Print ISBN: 978-3-319-28695-2

Electronic ISBN: 978-3-319-28697-6

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-28697-6_5